Search in Rotated Sorted Array

JavaView on GFG

Intuition

Search in sorted array rotated at an unknown pivot. Modified binary search.

Algorithm

1Find which half is sorted. If target in sorted half: search there. Else search other half.

Common Pitfalls

•Same as LC 33. One half is always sorted. Determine which using arr[lo] vs arr[mid]. O(log n).

Search in Rotated Sorted Array.java

Java

// Approach: Binary search. Determine which half is sorted, then narrow the search accordingly.
// Time: O(log n) Space: O(1)
class Solution {
    int search(int[] arr, int key) {
        int low = 0, high = arr.length - 1;

        while (low < high) {
            int mid = (low + high) / 2;
            if (arr[mid] > arr[high]) {
                if (arr[mid] < key || key <= arr[high])
                    low = mid + 1;
                else
                    high = mid;
            } else {
                if (arr[mid] < key && key <= arr[high])
                    low = mid + 1;
                else
                    high = mid;
            }
        }

        if (low == high && key != arr[low])
            return -1;

        return low;
    }
}

Was this solution helpful?