Array Binary Search

Search for a Range

10行code一次AC, beats 84.98%, time complexity logn+k, worst case O(n)

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int pos = Arrays.binarySearch(nums, 0, nums.length, target);
        if(pos<0) return new int[]{-1, -1};
        int left = pos;
        while(left>=0 && nums[left]==target) left--;
        int right = pos;
        while(right<nums.length && nums[right]==target) right++;
        return new int[]{left+1, right-1};
    }
}

binarySearch两次, 一次找左边界, 一次找右边界. 注意找左边界时, 如果找到target, 不能停止, 将right设置为mid-1后继续搜索.

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[] {-1,-1};
        if(nums==null || nums.length==0) return ans;
        if(target<nums[0] || target>nums[nums.length-1]) 
            return ans;
        int left =0; int right = nums.length-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(target==nums[mid]){
                if(mid==0 || nums[mid-1]!=target)
                    {ans[0] = mid;break;}
                right = mid-1; //key point
            }
            else if(target<nums[mid])
                right = mid-1;
            else
                left = mid+1;
        }
        left =0; right = nums.length-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(target==nums[mid]){
                if(mid==nums.length-1 || nums[mid+1]!=target){
                    ans[1] = mid; break;   
                }
                left = mid+1; //key point
            }
            else if(target<nums[mid])
                right = mid-1;
            else
                left = mid+1;
        }

        return ans; //set ans[-1, -1 ] at beginning, if ans is not assign value, return -1,-1
    }
}

First Bad Version

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int start = 1; int end = n;
        while(start<=end){
            int mid = start + (end-start)/2;
            if(isBadVersion(mid)){
                if(mid==1 || !isBadVersion(mid-1) )
                    return mid;
                end = mid;
            }
            else
                start = mid+1;
        }
        return end;
    }
}

Search Insert Position

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

Search in Rotated Sorted Array

这题有重复元素其实也可以

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

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

public class Solution {
    public int search(int[] nums, int target) {
        int start = 0; int end = nums.length-1;
        while(start<=end){
            int mid = start + (end-start)/2;
            if(nums[mid] == target) return mid;
            if(nums[start]<=nums[mid]){//keypoint <= can solve duplicate
                if(target>=nums[start] && target < nums[mid]) //keypoint <=
                    end = mid-1;
                else
                    start = mid+1;
            }
            else{
                if(target>nums[mid] && target<=nums[end]) //keypoint target<=
                    start = mid+1;
                else
                    end = mid-1;
            }
        }
        return -1;
    }
}

Find Minimum in Rotated Sorted Array

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

Find Minimum in Rotated Sorted Array II

写了一个递归的, 一次AC. 这题标注是hard, 一切反动派都是纸老虎.

只要单调(nums[start] < nums[end]), 就返回start.

public class Solution {
    public int findMin(int[] nums) {
        int min = search(nums, 0, nums.length-1);
        return min;
    }

    public int search(int[] nums, int start, int end){
        if(start>nums.length-1 || end<0 || start>end) return Integer.MAX_VALUE;
        if(nums[start]<nums[end] || start==end) return nums[start];
        else{
            int mid = start + (end-start)/2;
            int left = search(nums, start, mid);
            int right = search(nums, mid+1, end);
            return Math.min(left, right);
        }
    }
}

加上有重复元素的条件之后，这题立刻就变成 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]);
    }
}