Revised Binary Search


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

    }


  • 12
    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

  • 17
    M

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


  • 2

    @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.


  • 0
    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


  • 3
    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.


Log in to reply
 

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