1. 題目

搜索旋轉(zhuǎn)數(shù)組。給定一個(gè)排序后的數(shù)組，包含n個(gè)整數(shù)，但這個(gè)數(shù)組已被旋轉(zhuǎn)過很多次了，次數(shù)不詳。
請編寫代碼找出數(shù)組中的某個(gè)元素，假設(shè)數(shù)組元素原先是按升序排列的。若有多個(gè)相同元素，返回索引值最小的一個(gè)。

示例1:輸入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5輸出: 8（元素5在該數(shù)組中的索引）示例2:輸入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11輸出：-1 （沒有找到）提示: arr 長度范圍在[1, 1000000]之間

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/search-rotate-array-lcci
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

類似題目：LeetCode 81. 搜索旋轉(zhuǎn)排序數(shù)組 II（二分查找）

class Solution { public:int search(vector<int>& arr, int target) {int l = 0, r = arr.size()-1, mid;while(l < r)//無等號{mid = l+((r-l)>>1);if(arr[l] == arr[mid]){if(arr[l] == target)r = l;//上面while有等號，這里可能死循環(huán)elsel++;}else if(arr[l] > arr[mid])//左邊不是升序{if(arr[l] <= target || target <= arr[mid])r = mid;elsel = mid+1;}else if(arr[l] < arr[mid])//左邊是升序{if(arr[l] <= target && target <= arr[mid])r = mid;elsel = mid+1;}}return arr[l]==target ? l : -1;} };

44 ms 12.4 MB

總結(jié)

以上是生活随笔為你收集整理的程序员面试金典 - 面试题 10.03. 搜索旋转数组（二分查找）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。