网站怎么进入后台维护,公司网站建设价格低,深圳市住房和建设局工程交易服务中心,珠江网站建设1. 题目
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如#xff0c;数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值#xff0c;如果数组中存在这个目标值#xff0c;则返回它的索引#xff0c;否则返回 -1 。
你可以假设数…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(vectorint 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 mid1;}else if(nums[left] nums[mid]) //右边有序{if(nums[mid] target target nums[right])left mid1;elseright mid-1;}elseleft;}return -1;}
};测试数据
[9,5,6,7,8,9,9,9,9,9,9]
8
