【算法】二分排序和二分查找

二分排序和二分查找

一、二分查找

/**
	 *@title: binarySearch 
	 *@description: 二分查找（参数数组必须有序）
	 *@date: 2019年12月21日 上午10:37:25
	 *@param arrayA 有序数组
	 *@param key 关键元素
	 *@return int 关键元素在数组中的下标
	 */
	public static int binarySearch(int[] arrayA, int key) {
		int low = 0;
		int high = arrayA.length - 1;
		int mid = 0;

		while (low <= high) {
			mid = (low + high) / 2;

			if (key < arrayA[mid]) {
				high = mid - 1;
			} else if (key > arrayA[mid]) {
				low = mid + 1;
			} else
				break;
		}

		return mid;
	}

二、二分排序

参考：

https://www.jianshu.com/p/677359c1cc15

代码：

/**
	  *@title: binarySort 
	  *@description: 二分排序：总共有N个元素。
	  *当插入第i个元素时，对前面的0~i-1个元素使用二分法，
	  *找到该元素插入位置（相当于在有序数组中，一个一个插入新数值）
	  *@date: 2019年12月21日 下午12:09:27
	  *@param array 待排序数组
 	  *@return int[] 排序后的数组
	  */
	public static int[] binarySort(int[] array) {

		for (int i = 1; i < array.length; i++) {
			int temp = array[i];
			int low = 0;
			int high = i - 1;
			int mid = -1;

			while (low <= high) {
				mid = (low + high) / 2;

				if (temp < array[mid]) {
					high = mid - 1;
				} else { // temp >= array[mid])
					low = mid + 1;
				}
			}

			// 将low下标以后的元素全部向后移一位
			for (int j = i - 1; j >= low; j--) {
				array[j + 1] = array[j];
			}

			if (low != i)// 若待插入元素的插入位置不等于当前位置，则插入
				array[low] = temp;
		}

		return array;
	}

注意 二分排序与二分查找的区别：

两者的while循环内部不同，二分排序中判定相等不需要跳出循环

【二分排序】跳出循环后下标low标识关键元素需要插入的位置。