题目链接
题解一：暴力解法，遍历一遍数组，时间复杂度:O(n)
代码如下：
class Solution {
public:
int search(vector& nums, int target) {
for(int i = 0;i < nums.size();i++)
{
if(nums[i] == target) return i;
}
return -1;
}
};
题解二：题目要求时间复杂度为:O(logn)，一般有序数组的我们可以用二分查找来做
代码如下：
class Solution {
public:
int search(vector& nums, int target) {
if(nums.empty()) return -1;
//1.先找到分界点
int l = 0,r = nums.size() - 1;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(nums[mid] >= nums[0]) l = mid;
else r = mid - 1;
}
//2.找到target在哪段区间
if(target >= nums[0]) l = 0; //只需要更新左端点，右端点不用变
else l = r + 1, r = nums.size()-1;//说明target在[r+1,nums.size()-1]
//3.在2段区间内再次使用2分
while(l < r)
{
int mid = l + r >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
//找到返回r,没找到返回-1
if(target == nums[r]) return r;
return -1;
}
};
时间复杂度;O(logn)
空间复杂度:O(1)
