程序员面试金典 - 面试题 10.03. 搜索旋转数组（二分查找）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了程序员面试金典 - 面试题 10.03. 搜索旋转数组（二分查找），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1147字，纯文字阅读大概需要2分钟。

内容图文

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-cn.com/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有等号，这里可能死循环
    			else
    				l++;
    		}
    		else if(arr[l] > arr[mid])//左边不是升序
    		{
    			if(arr[l] <= target || target <= arr[mid])
    				r = mid;
    			else
    				l = mid+1;
    		}
    		else if(arr[l] < arr[mid])//左边是升序
    		{
    			if(arr[l] <= target && target <= arr[mid])
    				r = mid;
    			else
    				l = mid+1;
    		}
    	}
    	return arr[l]==target ? l : -1;
    }
};

44 ms 12.4 MB

内容总结

以上是互联网集市为您收集整理的程序员面试金典 - 面试题 10.03. 搜索旋转数组（二分查找）全部内容，希望文章能够帮你解决程序员面试金典 - 面试题 10.03. 搜索旋转数组（二分查找）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---