Interview Note - Binary Search & Sorted Array

Binary Search

For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.
If the target number does not exist in the array, return -1.
Example:
If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

class Solution {
    public int binarySearch(int[] nums, int target) {
        if(nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0;
        int end = nums.length - 1;
        while(start < end) {
            int mid = start + (end - start) / 2;
            if(nums[mid] >= target) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }

        return nums[start] == target ? start : -1;
    }
}

Key Points:

1. while(start < end): when start and end are overlapped each other, break. At this moment, we can return start or end. But it is different when we need to return the index before or after the target(see point 3).
2. int mid = start + (end - start) / 2: in order to avoid overflow of start + end, we need to do a little trick here.
3. while loop: in the while loop, there are two different needs:

• return the index of the target: as the example above.
• return the one before(example below)/after the target:
  Search Insert Position

  while(start <= end) {
      int mid = start + (end - start) / 2;
      if(A[mid] == target) {
          return mid;
      } else if(A[mid] < target) {
          start = mid + 1;
      } else {
          end = mid - 1;
      }
  }

  Here, we need to use while(start <= end) so that when we break the loop, two pointers are at two different(but neighbored) positions. Besides, if we want to return the one before the index, we return start, otherwise we return end.

Read More