Revised Binary Search


  • 144
    J
    public class Solution {
    public int search(int[] A, int target) {
        int lo = 0;
        int hi = A.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (A[mid] == target) return mid;
            
            if (A[lo] <= A[mid]) {
                if (target >= A[lo] && target < A[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (target > A[mid] && target <= A[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return A[lo] == target ? lo : -1;
    }
    

    }


  • 13
    J

    Notice that there is always a half of the array sorted, so we only need to see whether the target is in the sorted part or rotated part


  • 0
    W

    Good! Your solution is more simple than mine! I spend two much to see whether the target is in the sorted part or not


  • 0
    S

    Hi I used almost the same solution as yours, except written in python. But it seems to be extremly slow in the scoreboard(beat 20% submission). Is that the same case for you?


  • -1
    T

    same idea! python version

    def search(self, nums, target):
            l, r = 0, len(nums)
            while l < r:
                mid = (l + r) / 2
                if nums[mid] == target: return mid
                if target > nums[mid]:
                    if nums[mid] < nums[0] and target >= nums[0]:
                        r = mid
                    else:
                        l = mid + 1
                else:
                    if nums[mid] >= nums[0] and target < nums[0]:
                        l = mid + 1
                    else:
                        r = mid
            return -1

  • -1
    J

  • 19
    M

    If you change your while condition to lo<=hi, then you will simply need to return just -1 in the end.


  • 3

    @jerry13466 said in Revised Binary Search:

    int mid = (lo + hi) / 2;

    It would be better to use

    int mid = lo + (hi - lo) / 2;

    because if lo and hi are very large, (lo + hi) might potentially cause overflow.


  • 1
    M

    Same idea here but without that many conditionals:

    public class Solution {
        public int search(int[] nums, int target) {
            int lo = 0, hi = nums.length - 1;
            
            while(lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if(nums[mid] == target) return mid;
                if(nums[lo] <= target && target < nums[mid] 
                    || (nums[mid] < nums[hi] && (target > nums[hi] || target < nums[mid]))) {
                    hi = mid - 1;
                }else{
                    lo = mid + 1;
                }
            }
              
            return -1; 
        }
    }
    

  • 0
    R

    Javascript version:

    var search = function(nums, target) {
        if(nums.length == 0) return -1;
            var lo = 0, hi = nums.length - 1;
            var A = nums;
            while(lo < hi) {
                var mid = ((lo + hi) / 2) | 0;
                if(A[mid] == target) return mid;
                
                if(A[lo] <= A[mid]) {
                    if(target >= A[lo] && target < A[mid]) {
                        hi = mid -1;
                    } else {
                        lo = mid + 1;
                    }
                } else {
                    if(target > A[mid] && target <= A[hi]) {
                        lo = mid + 1;
                    } else {
                        hi = mid - 1;
                    }
                }
            }
            return A[lo] == target ? lo : -1;
    };
    

  • 1
    N

    @jerry13466 Somehow this now gives ArrayIndexOutOfBoundsException for the return statement.


  • 0
    N

    @BryanBo.Cao Tried this, but it goes TLE for input [1, 3] 2


  • 4
    T

    Thanks @jerry13466

    Quick question, why do you have the = sign in if (A[lo] <= A[mid]) (so covering the equal case in the if clause vs. the else clause). I tried without the equal sign and it does not work for some edge cases but I want to know your reasoning behind this.


  • 1
    S

    @tuanledang1120

    I have this question too! When right==left + 1, we will get mid == left. And we have already checked if nums[mid] == target, so at that time nums[right] is to be checked. At chat time, target >= nums[left] && target < nums[mid] and target > nums[mid] && target <= nums[right] are both false. We need left++ so we put the = at nums[left] <= nums[mid].

    And I have test if I change mid = (left + right) / 2 to mid = (left + right + 1) / 2, put = to the other inequality is OK.


  • 0
    J
    if (nums == null || nums.length == 0) {
                return -1;
            }
    

    I think this code should be added in order to avoid ArrayIndexOutOfBoundsException.


  • 0
    J

    @nvinchh add this,then it will work.

    if (nums == null || nums.length == 0) {
                return -1;
            }
    

  • 0
    A

    @jerry13466 emm... I guess you should take that the array is empty into consideration.


  • 0
    V
    This post is deleted!

  • 0
    N

    @jerry13466 the same idea.

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

  • 0
    R

    @showskyzt Thanks for your explanation! But I still cannot understand why "target > nums[mid] && target <= nums[right]" is false. In this case, left + 1 == right, so the first condition is false, but for the second, target > nums[left] && target <= nums[right] can happen, in this case, target == nums[right].
    ------------UPDATE-----------------
    OK, I think you put an assumption that target < nums[left]


Log in to reply
 

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