1. 題目

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。

( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。

搜索一個給定的目標值，如果數組中存在這個目標值，則返回它的索引，否則返回 -1 。

你可以假設數組中不存在重復的元素。

你的算法時間復雜度必須是 O(log n) 級別。

2. 解題

參考我的博客 二分查找

循環數組性質：以數組中間點為分區，數組分成一個有序數組和一個循環有序數組。

如果首元素 arr[low] < arr[mid]，左半部分：有序，右半部分：循環有序；
如果首元素 arr[low] > arr[mid]，右半部分：有序，左半部分：循環有序；
判斷查找的數是否在有序的半邊范圍內，更新上下限

class Solution { public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size()-1, mid;while(left <= right) {mid = left+((right-left)>>1);if(nums[mid] == target)return mid;if(nums[left] < nums[mid])//左邊有序 {if(nums[left] <= target && target < nums[mid])right = mid-1;elseleft = mid+1;}else if(nums[left] > nums[mid]) //右邊有序{if(nums[mid] < target && target <= nums[right])left = mid+1;elseright = mid-1;}elseleft++;}return -1;} }; 測試數據 [9,5,6,7,8,9,9,9,9,9,9] 8

總結

以上是生活随笔為你收集整理的LeetCode 33. 搜索旋转排序数组（二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。