Binary Search Note

Question Type:

• Find the any/first/last position of target in nums.
• Find Minimum in Rotated Sorted Array
• Search in Rotated Sorted Array
• 进一步理解二分法，保留有答案的那一半 (Eg: Find Peak Element)
• determine the answer should be guaranteed to be in one of the halves.
• there has to be a comparison operation about 'mid' elements ** Compare to target / leftmost / rightmost / neighbor ... etc.
• Closest / smallest larger than / largest smaller than / smallest larger or equals / largest smaller or equals / first occurrence / last occurrence ...
• We do not even know the right/left boundary of the sequence. Search in unknown sized array.

理解二分法的三个层次

• 头尾指针，取中点，判断往哪儿走
• 寻找满足某个条件的第一个或最后一个位置
• 保留剩下的一定有解的那一半

Time Complexity in Coding Interview

• O(1) 极少
• O(logn)几乎是二分法
• O(n^(1/2)) 几乎是分解质因数 （？？？）
• O(n) 高频
• O(nlogn) 一般都可能要排序
• O(n^2) 数组，枚举，动态规划
• O(n^3) 数组，枚举，动态规划
• O(2^n) 与组合有关的搜索
• O(n!) 与排列有关的搜索

Binary Search Common Template

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;
}

Template II

public int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (array[mid] < target) {
            left = mid + 1;
        } else if (array[mid] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
}

Sample questions

• Classical Binary Search (http://www.lintcode.com/en/problem/classical-binary-search/)
• First Position of Target (http://www.lintcode.com/en/problem/first-position-of-target/) Solution: if the nums[mid] >= target, right = mid; else left = mid;
• Search a 2D Matrix (https://leetcode.com/problems/search-a-2d-matrix/description/) (We can do this by using BinarySearch)
• Search a 2D Matrix II (https://leetcode.com/problems/search-a-2d-matrix-ii/description/)
• 35. Search Insert Position
• Sqrt(x)
• 278. First Bad Version
• 162. Find Peak Element (Notice: You should compare mid with mid + 1 and mid - 1, rather than left and right.)
• [L-small]一个数字在一个排好序的数组里面出现了> 1/4，求这个数 （数字必然是1/4， 2/3， 3/4 位置，用binarySearch 找到left，right 边界，进而计算size）
• 658. Find K Closest Elements

Rotated questions

• 153. Find Minimum in Rotated Sorted Array
• Find Minimum in Rotated Sorted Array II
• 33. Search in Rotated Sorted Array (Need to notice >= rather than >)
• 81. Search in Rotated Sorted Array II (Same with the last question. The solution is to compare if nums[left] < nums[mid] first. and if yes, then compare if target is between left and mid. You should compare nums[left], nums[right] directly. It is meaningless.)

Binary Search Variant 2.0

• Given a integer dictionary A of unknown size, where the numbers in the dictionary are sorted in ascending order, determine if a given target integer T is in the dictionary. Return the index of T in A, return -1 if T is not in A. (https://code.laioffer.com/editor/20/) Solution:

1. find the right idx. Two termination conditions (1. dict.get(idx) == null 2. dict.get(idx) >= target)
2. use binarySearch to find the result.