23-Search-in-Rotated-Sorted-Array.md

Search in Rotated Sorted Array

Problem Link

https://leetcode.com/problems/search-in-rotated-sorted-array/

---

Pattern

• Binary Search

---

Approach

Modified binary search: determine which half is sorted and decide where target may lie, then adjust bounds.

---

Time Complexity

O(log n)

Space Complexity

O(1)

---

Java Solution

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] == target) return m;
            if (nums[l] <= nums[m]) {
                if (target >= nums[l] && target < nums[m]) r = m - 1;
                else l = m + 1;
            } else {
                if (target > nums[m] && target <= nums[r]) l = m + 1;
                else r = m - 1;
            }
        }
        return -1;
    }
}