Blog Details

Binary search – locate target fast in O(logn)

1. Limitation of Binary Search

  • The data structure must be array, and sorted in certain order.
  • Data size too small or too big is not reasonable to use binary search.

2. Cases of using binary search

2.1 Find the target in the sorted list

Input: [1, 3, 4, 5, 8, 10]
Target: 3
Output: 1
Target: 9
Output: -1

Here is the solution:

public int binarySearch(int[] nums, int target) {
	int low = 0;
	int high = nums.length - 1;
	while(low <= high) {
		int mid = low + ((high - low) >> 1);
		if(nums[mid] > target) {
			high = mid - 1;
		} else if(nums[mid] < target) {
			low = mid + 1;
		} else {
			return mid;
		}
	}
	return -1;
}

2.2 Find the first target in the repeated sorted list

Input: [1, 2, 2, 3, 3, 3, 4, 5, 6]
Target: 3
Output: 3

Check the solution below:

// Find first target
public int findFirstTarget(int[] nums, int target) {
	int low = 0;
	int high = nums.length - 1;
	
	while(low <= high) {
		int mid = low + ((high - low) >> 1);
		if(nums[mid] > target) {
			high = mid - 1;
		} else if(nums[mid] < target) {
			low = mid + 1;
		} else {
			if(mid == 0 || nums[mid - 1] != target) {
				return mid;
			} else {
				high = mid - 1;
			}
		}
	}
	return -1;
}

2.3 Find the last target in the repeated sorted list

Input: [1, 2, 2, 3, 3, 3, 4, 5, 6]
Target: 3
Output: 5

Solution:

// Find last target in the list
public int findLastTarget(int[] nums, int target) {
	int low = 0; 
	int high = nums.length - 1;
	while(low <= high) {
		int mid = low + ((high - low) >> 1);
		if(nums[mid] > target) {
			high = mid - 1;
		} else if(nums[mid] < target) {
			low = mid + 1;
		} else {
			if(mid == nums.length - 1 || nums[mid + 1] != target) {
				return mid;
			} else {
				low = mid + 1;
			}
		}
	}
	return -1;
}

2.4 Find the position of first element that greater than target

Input: [1, 2, 2, 4, 4, 5, 6, 8, 10]
Target: 4
Output: 5
Target: 2
Output: 3

Solution:

// Find first position > target
/*
 * Input: 1, 2, 2, 4, 4, 5, 6, 8, 10
 * Target: 4
 * Output: 5 
 * Target: 2
 * Output: 3
 */
public int findFirstGreater(int[] nums, int target) {
	int low = 0;
	int high = nums.length - 1;
	while(low <= high) {
		int mid = low + ((high - low) >> 1);
		if(nums[mid] > target) {
			high = mid - 1;
		} else {
			if(nums[mid + 1] > target) {
				return mid + 1;
			} 
			if(mid == nums.length - 1) {
				return - 1;
			}
			low = mid + 1;
		}
	}
	return -1;
}

2.5 Find first position < target

// Find last less than target
public int findLastLess(int[] nums, int target) {
	int low = 0;
	int high = nums.length - 1;
	while(low <= high) {
		int mid = low + ((high - low) >> 1);
		if(nums[mid] > target) {
			high = mid - 1;
		} else {
			if(mid == 0) {
				return -1;
			}
			if(nums[mid - 1] < target && nums[mid] == target) {
				return mid - 1;
			}
			low = mid + 1;
		}
	}
	return -1;
}