龙口做网站es158百度站长工具平台登录

搜索旋转数组。给定一个排序后的数组，包含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 （没有找到）

代码如下：

//二分查找法--数组有序
class Solution {
public:int search(vector<int>& arr, int target) {int n=arr.size();if(arr[0]==target){return 0;}  int left=0;int right=n-1;while(left<=right){int mid=left+(right-left)/2;if(arr[mid]==target)//含有重复值{while(mid>1&&arr[mid-1]==arr[mid]){mid--;}return mid;}else if(arr[left]>arr[mid])//如果arr[left]>arr[mid]说明数组在arr[mid]和arr[right]之间是有序的{if(target>arr[mid]&&target<=arr[right])//当target在arr[mid]与arr[right]之间时，使用二分查找{left=mid+1;}else{right=mid-1;}}else if(arr[left]<arr[mid])//如果arr[left]<arr[mid]说明数组在arr[left]和arr[mid]之间是有序的{if(target>=arr[left]&&target<arr[mid])//当target在arr[left]与arr[mid]之间时，使用二分查找{right=mid-1;}else{left=mid+1;}}else{left++;//数组中有重复时，并且nums[left]!=target}}return -1;}
};