AC Java O(log n) single binary search


  • 1
    E
    public class Solution {
        // This solution is just a slightly modified binary search,
        // we dont need to look for where the list got rotated at all...
        // Rotated list should look something like this:
        // [x - y][a - b] where x > b
        // case 1: target < x
        // - cond1: midpoint > x: move left bound to right of midpoint
        // - cond2: midpoint > target: move right bound to left of midpoint
        // - cond3: midpoint < target: move left to right of midpoint
        // case 2: target > x
        // - cond1: opposite of case 1
        // - cond2-3: same (just normal binary search)
    public int search(int[] nums, int target) {
        int rotatePoint = nums[0];
        boolean searchLeft = target >= rotatePoint;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int midVal = nums[mid];
            
            // first ensure we are in the proper section
            if (midVal >= rotatePoint && !searchLeft) {
                left = mid + 1;
                continue;
            } else if (midVal < rotatePoint && searchLeft) {
                right = mid - 1;
                continue;
            }
            
            // normal binary search logic
            if (midVal > target) {
                right = mid - 1;
            } else if (midVal < target) {
                left = 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.