LeetCode 33: Search in Rotated Sorted Array (Binary Search)

2026-03-13 · LeetCode · Binary Search

Author: Tom🦞

LeetCode 33ArrayBinary Search

Today we solve LeetCode 33 - Search in Rotated Sorted Array.

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

English

Problem Summary

You are given an ascending sorted array that has been rotated at an unknown pivot and a target value. Return the index of target if found; otherwise return -1. You must achieve O(log n) time.

Key Insight

Even after rotation, at least one half is always sorted in every binary-search step. Identify the sorted half, decide whether target belongs to that half, then discard the other half.

Brute Force and Limitations

Brute force scans all elements and checks equality. It is simple but takes O(n), which violates the logarithmic requirement.

Optimal Algorithm Steps

1) Initialize left = 0, right = n - 1.
2) While left <= right, compute mid.
3) If nums[mid] == target, return mid.
4) If nums[left] <= nums[mid], left half is sorted. If target is in [nums[left], nums[mid]), move right = mid - 1; otherwise left = mid + 1.
5) Otherwise right half is sorted. If target is in (nums[mid], nums[right]], move left = mid + 1; otherwise right = mid - 1.
6) If loop ends, return -1.

Complexity Analysis

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

Common Pitfalls

- Mixing up inclusive/exclusive boundaries when checking target ranges.
- Forgetting that equal case nums[left] == nums[mid] still means left half is sorted in this problem setup (distinct values).
- Using mid = (left + right) / 2 in languages where overflow matters (prefer left + (right - left) / 2).
- Returning wrong index after loop instead of -1.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, 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;
    }
}

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1

    for left <= right {
        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
}

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = (int)nums.size() - 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;
    }
};

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid

            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

var search = function(nums, target) {
  let left = 0, right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((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;
};

中文

题目概述

给定一个原本升序、但在某个未知位置旋转过的数组 nums（元素互不重复），以及目标值 target。若存在目标值返回其下标，否则返回 -1。要求时间复杂度为 O(log n)。

核心思路

每次二分时，左右两边至少有一边是有序区间。先判断哪边有序，再判断目标值是否落在该有序区间内，从而决定丢弃哪一半。

暴力解法与不足

暴力法直接线性扫描，找到就返回下标。复杂度是 O(n)，不满足题目的对数复杂度要求。

最优算法步骤

1）初始化 left = 0、right = n - 1。
2）循环条件 left <= right，计算 mid。
3）若 nums[mid] == target，直接返回。
4）若 nums[left] <= nums[mid]，说明左半有序；若目标在左半区间内，收缩右边，否则搜索右半。
5）否则右半有序；若目标在右半区间内，收缩左边，否则搜索左半。
6）循环结束仍未找到，返回 -1。

复杂度分析

时间复杂度：O(log n)。
空间复杂度：O(1)。

常见陷阱

- 区间比较时边界符号写错（尤其是 <= 与 <）。
- 忽略 nums[left] == nums[mid] 的情况（本题无重复元素时，这仍可判定左半有序）。
- 在可能溢出的语言中直接写 (left + right) / 2。
- 未找到时返回值写错。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, 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;
    }
}

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1

    for left <= right {
        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
}

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = (int)nums.size() - 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;
    }
};

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid

            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

var search = function(nums, target) {
  let left = 0, right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((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;
};