Binary Search

We basically ignore half of the elements just after one comparison. Compare x with the middle element. If x matches with middle element, we return the mid index. Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half. Else (x is smaller) recur for the left half.

1. Regular Binary Search:

return the index of the target number in a sorted array, if there is no such a number, return -1;

input: data = [1, 2, 3],

key = 0, 1, 2, 3, 4

output: res = -1, 0, 1, 2, -1

public int binarySearch(int[] data, int key) {
	int low = 0;
	int high = data.length - 1;      
	while(high >= low) {
		int middle = (low + high) / 2;
		if(data[middle] == key) {
			return middle;
		}
		if(data[middle] < key) {
			low = middle + 1;
		}
		if(data[middle] > key) {
			high = middle - 1;
		}
	}
	return -1;
}

2. Find the position

Given an array containing distinct elements, use the given number to substitute a number in a sorted array, find the right position for this given number which makes the array after replacement still sorted.

input: data = [3, 4, 6],

key = 0, 2, 3, 5, 8

output: res = 0, 0, 0, 1, 2

explain: for key = 0, if it is inserted into the input array, it should be at the first position.

public int binarySearchForReplacement(int[] data, int key) {
	int low = 0;
	int high = data.length - 1;      
	while(high >= low) {
		int middle = (low + high) / 2;
		if(data[middle] == key) {
			return middle;
		}
		if(data[middle] < key) {
			low = middle + 1;
		}
		if(data[middle] > key) {
			high = middle - 1;
		}
	}
	return low - 1 < 0 ? 0 : low - 1;                 // the only difference compared with the above code
}

int this case, the largest number less or equal than key would be replaced. change return low - 1 to low, can have the least number greater than key been replaced

See Problem #74. Search a 2D Matrix

3. Find The Upper Bound and Lower Bound using Binary Search

The lower and upper bound of a binary search are the lowest and highest position where the value could be inserted without breaking the ordering.

Take, for example, a sorted range
1 2 3 4 5 5 5 6 7 9
In a binary search for 3, we will have
   v-- lower bound
1 2 3 4 5 5 5 6 7 9
     ^-- upper bound
And in a binary search for 5:
       v-- lower bound
1 2 3 4 5 5 5 6 7 9
             ^-- upper bound

public int binarySearchForUpperbound(int[] data, int key) {
	int low = 0;
	int high = data.length;      
	while(high > low) {
		int middle = (low + high) / 2;
		if(data[middle] <= key) {
			low = middle + 1;
		}else{
			high = middle;
		}
	}
	return low;               // the only difference compared with the above code
}

public int binarySearchForLowerBound(int[] data, int key) {
	int low = 0;
	int high = data.length;      
	while(high > low) {
		int middle = (low + high) / 2;
		if(data[middle] >= key) {
			high = middle;
		}else{
			low = middle + 1;
		}
	}
	return low;               // the only difference compared with the above code
}

4. Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while(low < high){
            int middle = (low + high) / 2;
            if(nums[middle] < nums[nums.length - 1]){
                high = middle;
            }else{
                low = middle + 1;
            }
        }
        return nums[low];
}

If the array may contain duplicates.

public int findMin(int[] num) {
        int lo = 0;
        int hi = num.length - 1;  
        while(lo < hi) {
            int mid = lo + (hi - lo) / 2;        
            if (num[mid] > num[hi]) {
                lo = mid + 1;
            }
            else if (num[mid] < num[hi]) {
                hi = mid;
            }
            else { // when num[mid] and num[hi] are same
                hi--;
            }
        }
        return num[lo];
}

See Problem #153. Find Minimum in Rotated Sorted Array

See Problem #154. Find Minimum in Rotated Sorted Array II