Array Binary Search

Search for a Range

典型的 binary search 题，我还是比较喜欢用 left + 1 < right，不用担心各种奇葩输入导致的越界。

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftEnd = left, rightEnd = right;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target){
                right = mid;
            } else {
                left = mid;
            }
        }
        if(nums[left] == target) leftEnd = left;
        else if(nums[right] == target) leftEnd = right;
        else leftEnd = -1;

        left = 0;
        right = nums.length - 1;

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

        int[] rst = new int[2];
        rst[0] = leftEnd;
        rst[1] = rightEnd;

        return rst;
    }
}

First Bad Version

这道不是 LinkedIn 面经题。

是我被 DP 虐多了之后，来无耻地灌个水找找自信。。

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(isBadVersion(mid)){
                right = mid;
            } else {
                left = mid;
            }
        }

        if(isBadVersion(left)) return left;
        else if(isBadVersion(right)) return right;

        return -1;
    }
}

Search Insert Position

这道不是 LinkedIn 面经题。

是我被 DP 虐多了之后，来无耻地灌个水找找自信。。

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            } else if(nums[mid] < target){
                left = mid;
            } else {
                right = mid;
            }
        }

        if(target <= nums[left]) return left;
        if(target <= nums[right]) return right;
        if(target > nums[right]) return right + 1;

        return 0;
    }
}

Search in Rotated Sorted Array

这题在地里看到过，当时把猴子给弄挂了。。

这题很重要的性质是，没有重复元素。

可以根据 A[mid] 与 A[right] 的大小关系，先行判断 mid 一定位于哪一端；

对于已经确定 mid 左/右 的数组，必然有一段区间满足单调性，可以利用来做 binary search.

public class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while(left + 1 < right){
            int mid = left + (right - left) / 2;

            if(nums[mid] >= nums[right]){
                if(target <= nums[mid] && target >= nums[left]){
                    right = mid;
                } else {
                    left = mid;
                }
            } else {
                if(target >= nums[mid] && target <= nums[right]){
                    left = mid;
                } else {
                    right = mid;
                }
            }
        }

        if(nums[left] == target) return left;
        if(nums[right] == target) return right;

        return -1;
    }
}

Find Minimum in Rotated Sorted Array

在把上一道题做完之后，这题就是一个乞丐版的 search in rotated sorted array. 因为已知没有 duplicates 就更简单了。

public class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

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

        return Math.min(nums[left], nums[right]);
    }
}

Find Minimum in Rotated Sorted Array II

加上有重复元素的条件之后，这题立刻就变成 Hard 难度了。原因在于出现了新情况，即我们不知道最小值到底在 mid 的左边还是右边，比如【3,[3],1,3】，中间的 3 和两端值都相等，无法正确地直接砍掉一半。

• 我们依然可以靠 A[mid] 与 A[right] 的大小关系来二分搜索；

  • A[mid] > A[right] 时，mid 在左半边，最小值一定在 mid 右侧；

  • A[mid] < A[right] 时，mid 在右半边，最小值一定在 mid 左侧；

• A[mid] == A[right] 时，无法判断，把 right 向左挪一格。

public class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

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

        return Math.min(nums[left], nums[right]);
    }
}