Java intuitive, closest to unflavored binary search


  • 7
    Y

    I have looked at popular solutions like this, this and this , and found that the top-level logic is not consistent with binary search, because they compare nums[left] or nums[right] against nums[mid], instead of against target.

    If we keep the logic of binary search, and just checking monotonicity inside the if block, the logic will be closest to unflavored binary search. Easier to understand and connect to binary search.

    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                // the left half is monotonic, yet still does not satisfy
                if (nums[left] <= nums[mid] && nums[left] > target) { 
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                // the right half is monotonic, yet still does not satisfy
                if (nums[right] >= nums[mid] && nums[right] < target) { 
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
    

Log in to reply
 

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