TikTok OA 面试真题解析：旋转排序数组中的搜索

Description:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand, for example, [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2].

You are given a target value to search. If found in the array, return its index; otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Input: nums = [1], target = 0
Output: -1

这道题要求在一个“原本有序、但经过旋转”的数组中查找目标值，并返回其下标；如果不存在则返回 -1。核心思路是二分查找：每次判断左半段或右半段是否仍然有序，再结合目标值所在区间缩小搜索范围，因此整体时间复杂度可以保持在 O(log n)。题目明确说明数组中没有重复元素，所以判断区间边界会更直接。