1. 题目
搜索旋转数组。给定一个排序后的数组,包含n个整数,但这个数组已被旋转过很多次了,次数不详。
请编写代码找出数组中的某个元素,假设数组元素原先是按升序排列的。若有多个相同元素,返回索引值最小的一个。
示例1:输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5输出: 8(元素5在该数组中的索引)示例2:输入:arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11输出:-1 (没有找到)提示:arr 长度范围在[1, 1000000]之间
来源:力扣(LeetCode)
链接:https://leetcode-/problems/search-rotate-array-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
类似题目:LeetCode 81. 搜索旋转排序数组 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有等号,这里可能死循环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