Binary search summary

Binary search template by jiuzhang

http://www.jiuzhang.com/solutions/binary-search/

Note: if question is not complex, try non-recursive method firstly, then recursive method, which depends on the interviewer.

When need Binary search?

• You need to optimize a brute-force method of O(n) to a better one
• Sorted array or rotated sorted array

How Binary search?

• Find first position of …
• Find last position of …

Key points:

• start + 1 < end: to have situations where only have start and end left, or one number (start/end) left
• mid = start + (end – start) / 2, to avoid the overflow problem, for example, start and and end are both a very large number close to the MAX_Integer
• To find the first, we need to specify two parts: if (nums[mid] == target) end = mid; then if (nums[start] == target) return start goes firstly.
• To find the last, we need to specify two parts: if (nums[mid] == target) start = mid; then if (nums[end] == target) return end goes firstly.

Four important points to notice:

• start + 1 < end
• start + (end – start) / 2
• A[mid] ==, <, >
• A[start] A[end] ? target

Non-recursive Binary search:

class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                end = mid;  
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}

Recursive Binary search:

  public static int binarySearch(int[] nums, int target) {
    return binarySearch(nums, 0, nums.length - 1, target);
  }

  private static int binarySearch(int[] nums, int start, int end, int target) {
    if (start > end)
      return -1;
    int mid = start + (end - start) / 2;

    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] < target) {
        return binarySearch(nums, mid + 1, end, target);
    }
    return binarySearch(nums, start, mid - 1, target);
  }