Easy to understand 1ms Java binary-search solution


  • 1
    M
    public class Solution {
    public int search(int[] nums, int target) {
        int pivot = findPivot(nums);
        if(pivot == 0) return binarySearch(nums, 0, nums.length - 1, target);
        int rightSide = binarySearch(nums, pivot, nums.length - 1, target);
        if(rightSide != -1) return rightSide;
        int leftSide = binarySearch(nums, 0, pivot - 1, target);
        return leftSide;
    }
    
    private int findPivot(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            if(nums[left] < nums[right]) return left;
            int mid = left + (right - left) / 2;
            if(nums[left] < nums[mid]) {
                left = mid + 1;
            } else if(nums[left] > nums[mid] && nums[mid] < nums[right]) {
                right = mid;
            } else {
                return right;
            }
        }
        return left;
    }
    
    private int binarySearch(int[] nums, int start, int end, int target) {
        if(start > end) return -1;
        int mid = start + (end - start) / 2;
        if(target == nums[mid]) return mid;
        if(target < nums[mid]) return binarySearch(nums, start, mid - 1, target);
        return binarySearch(nums, mid + 1, end, target);
    }
    
    }

  • 0
    T

    That's a lot of binary searches, like the simple idea. Is there any reason you mixed iterative and recursive binary searches?


  • 0
    M

    Well the findPivot function uses iterative, but its for different purpose. It's from another problem about finding the minimum element in sorted and rotated arrays (i think), so I just used that. And others are the regular binarySearch for three cases:

    1. the array is not rotated and element could be anywhere
    2. the array is rotated and the element is on the right side of the pivot
    3. the array is rotated and its not found on the right side, so it could be on the left.

    Actually the first two cases can be merged for conciseness. And yeah you are right i should have used iterative for the "regular binary search" as well for consistency.


Log in to reply
 

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