Search in Rotated Sorted Array

Why it belongs on this sheet

This is the interview version of binary search that checks whether you can still reason when the array is only partially ordered.

Pattern

Pick the sorted half

Approach

At every midpoint, one half must still be sorted. Detect which half is sorted and decide whether the target lies inside that half or the other one.

Java solution

class Solution {
  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;
      }

      if (nums[left] <= nums[mid]) {
        if (nums[left] <= target && target < nums[mid]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else {
        if (nums[mid] < target && target <= nums[right]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }

    return -1;
  }
}

Complexity

• Time: O(log n)
• Space: O(1)

Interview note

The key sentence is: "one side is always normally sorted, even after rotation."