Java solution with comments


  • 5
    T
    public boolean search(int[] A, int target) {
        int start = 0;
        int end = A.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (A[mid] == target) // case 0
                return true;
            // finally start == mid == end, if case 0, return true, else end the loop
            else if (A[start] == A[mid])
                start++;
            else if (A[end] == A[mid])
                end--;
            else if (A[start] <= target && target <= A[mid]) // case 1
                end = mid;
            else if (A[mid] < target && target <= A[end]) // case 2
                start = mid + 1;
            else if (A[start] > A[mid]) // case 2 is false, so target in this range
                end = mid;
            else   // case A[mid] > A[end] and case 1 is false, similar to above
                start = mid + 1;
        }
        return false;
    }

  • 0
    M

    int mid = (start + end ) / 2;


  • 1
    M

    We don't recommend to write code like this since it may overflow while code like start + (end - start) / 2 won't in any case.


  • 1
    K

    I am wondering why (start + end ) / 2 would overflow. Given the condition (start <= end),if the array needs to overflow, that means (end+start)/2 > end, which means start/2 > end/2 that's to say start > end. It doesn't follow the condition (start <= end so it will break up the loop.


Log in to reply
 

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