LeetCode-33.-搜索旋转排序数组二分法
目录
LeetCode–33. 搜索旋转排序数组(二分法)
搜索旋转排序数组(C）
1. 题目描述
难度： 中等
2. 题目分析
这道题我们需要关注的点有一下几个：
- 数组整体是 升序 的，并且数组中 不存在重复的元素
- 数组在某一点进行了 旋转
- 返回值是相同元素的 下标 ，没有则返回-1
- 算法时间复杂度必须是 O(logn)
从上面几点分析，要想时间复杂度达到 O(logn) ，要使用二分法进行搜索。但是怎么处理旋转之后的数组呢？对于旋转之后的数组我们可以用下面这个柱形图图来表示，柱形图的高相当于元素的值。以[4, 5, 6, 7, 0, 1, 2]为例：
从这张图可以看出：
- 最左边的元素 一定大于 最右的元素
- 如果 一个元素大于最右的元素 ，那么这个元素 一定 在区间[1, 4]之间，否则该元素 一定 在[5,7]之间
我们可以根据这两点来进行二分法的实现。
3. C语言实现
代码如下：
int search(int* nums, int numsSize, int target){
// 定义左节点，中间节点与右节点
int left, right, mid;
left = 0;
right = numsSize - 1;
// 进行二分法寻找
while(left <= right){
mid = (left+right)/2;
// 如果mid值与目标值相等的话，返回此刻的mid值
if (target == nums[mid])
return mid;
else if(nums[mid] > nums[right]){
if(target >= nums[left] && target < nums[mid]){
right = mid - 1;
}
else{
left = mid + 1;
}
}
else{
if(target > nums[mid] && target <= nums[right]){
left= mid + 1;
}
else{
right = mid - 1;
}
}
}
return -1;
}运行结果为：
