Java Super Clear Solution with Super Detailed Explanation (Took me 2 hours to write)


  • 3
    Y

    We all know how to do binary search. The only thing we need to find out is when we need to go the opposite way (compared to normal binary search). Suppose we have a center part of a rotated array:
    ... a b c x d e f g ...
    Let a be arr[lo] and g be arr[hi]. Binary search will find x as arr[mid]. Now we need to decide to search left or search right.

    Some basic knowledge:
    When dealing with rotated array, we search differently than normal binary search. We know x = arr[mid], and target > x or target < x, but in either case, target can still be on the left or right of x. We need more information to confirm where our target is.

    First thing is how to check if array is rotated: arr[lo] > arr[hi]. Done.

    Next, we want to check if x is on the left or right part of the rotated array. For example, given array [4, 5, 1, 2, 3], we define [4, 5] as the left part and [1, 2, 3] as the right part. Though the array is rotated, the left and right parts will remain sorted, so anything in the left part should be >= arr[lo], and anything in the right part should be < arr[lo]. But since arr[lo] > arr[hi] in a rotated array (without duplicates), for the left part, >= arr[lo] can be replaced by > arr[hi], and for the right part, < arr[lo] can be replaced by <= arr[hi]. Thus, if x >= arr[lo] or x > arr[hi] then x is in the left part, and if x < arr[lo] or x <= arr[hi] then x is in the right part.

    Finally, we want to check where our target belongs to. We have already proven that x >= arr[lo] or x > arr[hi] when x is in the left part, and x < arr[lo] or x <= arr[hi] when x is in the right part, and if we use it, we can see that target is in the left part when target >= arr[lo] or target > arr[hi], and target is in the right part if target < arr[lo] or target <= arr[hi].

    There are 3 cases:

    1. x > target.
      Now let's consider all possible cases:
      For rotated array:
      a) x and target both in left or right part. But since x > target, and left and right parts are both sorted, we have to go left to search for target.
      b) x is in left part and target is in right part. This is possible because x > target, and we know numbers in the left part > numbers in the right part. Thus to find target, we need to search to the right in this case.
      c) x is in right part and target is in left part. This is impossible since in rotated array, arr[lo] > arr[hi], and we already have x > target. This condition can be written as: array is rotated, x is in the left part, and target is in the right part, or equivalently nums[lo] > nums[hi] && target <= nums[hi] && nums[mid] >= nums[lo].
      For unrotated array:
      d) The array is not rotated, if we have x > target we simply search left for target.

    We found for case a and d, we search to the left. Only in case b do we search to the right. It boils down to:

    if (nums[mid] > target) {
        if (nums[lo] > nums[hi] && target <= nums[hi] && nums[mid] >= nums[lo]) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    
    1. x < target. In normal binary search we would need to search right. In rotated array we don't. The idea is the same as above. We want to find the "outlier" case when we search to the left. Cases can be:
      For rotated array:
      a) x and target both in left or right part. But since x < target, target can only be on right side of x.
      b) x in left and target in right. We have already proven that arr[lo] > arr[hi], and every element in left part should be greater than right part, so this is not possible.
      c) x in right and target in left, this is the only case where we need to search to the left because target is on the left side of x. The condition for this can be written as: array is rotated, and x is on the right part, and target is on the left part, which is equivalent to: nums[lo] > nums[hi] && target >= nums[lo] && nums[mid] <= nums[hi].
      For unrotated array:
      d) x < target implies x is on the left side of target, so we must go left.

    Thus it boils down to:

    else if (nums[mid] < target) {
        if (nums[lo] > nums[hi] && target >= nums[lo] && nums[mid] <= nums[hi]) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    
    1. x == target. We have found the target value. This is trivial.
    public class Solution {
        public int search(int[] nums, int target) {
            if (nums == null) return -1;
            int lo = 0, hi = nums.length-1;
            while (lo <= hi) {
                int mid = (hi-lo)/2 + lo;
                if (nums[mid] > target) {
                    if (nums[lo] > nums[hi] && target <= nums[hi] && nums[mid] >= nums[lo]) {
                        lo = mid + 1;
                    } else {
                        hi = mid - 1;
                    }
                } else if (nums[mid] < target) {
                    if (nums[lo] > nums[hi] && target >= nums[lo] && nums[mid] <= nums[hi]) {
                        hi = mid - 1;
                    } else {
                        lo = mid + 1;
                    }
                } else {
                    return mid;
                }
            }
            return -1;
        }
    }
    

Log in to reply
 

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