Concise O(log N) Binary search solution


  • 258
    L
    class Solution {
    public:
        int search(int A[], int n, int target) {
            int lo=0,hi=n-1;
            // find the index of the smallest value using binary search.
            // Loop will terminate since mid < hi, and lo or hi will shrink by at least 1.
            // Proof by contradiction that mid < hi: if mid==hi, then lo==hi and loop would have been terminated.
            while(lo<hi){
                int mid=(lo+hi)/2;
                if(A[mid]>A[hi]) lo=mid+1;
                else hi=mid;
            }
            // lo==hi is the index of the smallest value and also the number of places rotated.
            int rot=lo;
            lo=0;hi=n-1;
            // The usual binary search and accounting for rotation.
            while(lo<=hi){
                int mid=(lo+hi)/2;
                int realmid=(mid+rot)%n;
                if(A[realmid]==target)return realmid;
                if(A[realmid]<target)lo=mid+1;
                else hi=mid-1;
            }
            return -1;
        }
    };

  • -114
    H

    consider case: 4,4,4,4,0,1,2,4,how can you find the smallest value


  • 8
    L

    The problem states that no duplicate exist in the array


  • 8
    C

    I think its really clever to find the smallest element first. Thanks for sharing!


  • 0
    M

    I don't know why your lgN method is much slower than the O(n) method. yours is 44ms while the O(n) is 16ms


  • 0
    J

    the solution is really clever. I just thought out to find the min, but in binary search part, how to get the realmid is very clever. Thanks for sharing!


  • 1
    A

    The O(logN) method is faster than O(n) ,however the inputs should be large,for small inputs the latter one might be faster


  • 0
    A

    How will that code for [1],3 it should go forever,or am I wrong?


  • 3
    J

    How did you come up with binary search to find the minimum integer? Because intuitively binary search is for sorted list, but in this case it's not fully sorted.


  • 0
    P

    After you find the smallest one, you find the location of rotation and you will sort of get the original sorted array.

    Again, this idea is awesome!


  • 0
    O

    nice to learn!


  • 0
    R

    there is one problem in leetcode to find minimal integer in such array, you can check that one


  • 57
    K

    Well done! Based on your approach, I have beaten 100% of java submission. Here's my java code:

    public int search(int[] nums, int target) {
        int minIdx = findMinIdx(nums);
        if (target == nums[minIdx]) return minIdx;
        int m = nums.length;
        int start = (target <= nums[m - 1]) ? minIdx : 0;
        int end = (target > nums[m - 1]) ? minIdx : m - 1;
        
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) return mid;
            else if (target > nums[mid]) start = mid + 1;
            else end = mid - 1;
        }
        return -1;
    }
    
    public int findMinIdx(int[] nums) {
        int start = 0, end = nums.length - 1;
        while (start < end) {
            int mid = start + (end -  start) / 2;
            if (nums[mid] > nums[end]) start = mid + 1;
            else end = mid;
        }
    	return start;
    }

  • 7
    E

    I think the second while loop can be optimised. Given that you have already known the left hand sub array and the right hand sub array, so we don't have to set low = 0 and high = n - 1, we can set the arrange more precisely to [0 - smallest_index] or [smallest_index, high](whether in left hand or in right hand or not exists ). Am I right?


  • 0
    N

    what if you need to find value in n-1 elements after your optimization, which is less efficient than binary search.


  • 30
    R

    This code is much more readble:

    public class Solution {
    public int search(int[] nums, int target) {
        int start = 0, end = nums.length - 1;
        while (start < end) {
            int mid = (start + end) / 2;
            if (nums[mid] > nums[end]) {  // eg. 3,4,5,6,1,2
                if (target > nums[mid] || target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid;
                }
            } else {  // eg. 5,6,1,2,3,4
                if (target > nums[mid] && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid;
                }
            }
        }
        if (start == end && target != nums[start]) return -1;
        return start;
    }
    }

  • 0
    Z

    Is the performance of this double binary search algo is better than the single binary search algo in the link below? Why?
    https://leetcode.com/discuss/41134/java-ac-solution-using-once-binary-search


  • 0
    Z

    Is the performance of this double binary search algo is better than the single binary search algo in the link below? Why?
    https://leetcode.com/discuss/41134/java-ac-solution-using-once-binary-search


  • 2
    M

    upvoted! nice to learn this.


  • 0
    D

    How would you apply this when there are duplicated elements? such as the follow up question II.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.