一、折半查找原理
在生活中，我们去查英文字典，比如查 legacy
我们一般不会从 a 开始，而是从中间开始翻，如果找到 j ，然后看这个 l ,是在 a - j 中间 ，还是在 j - z 之间
之后再从对应的范围重复从中间开始找，再判断范围，直到找到那个词
从这里我们可以看到折半查找的原理：
在一个有序排列的数据中，查找数据 a
- 我们每次从中间开始查找，得到中间值 b
- 判断 a 和 b 的关系，随后缩小查找范围，最终找到数据 a
为了更好理解折半查找，我们讲解一个经典的例子
例子
假设我们要在一个有序数组中 比如 在 [2,5,8,12,15,17,19,22,25,32],找到 12, 找到了返回坐标，没找到返回 -1
因为有序，所以使用折半查找
折半查找，我们创建变量 mid，查找范围交给 left 和 right
mid = (0+9)/2 = 4 就是第五个值，
发现 mid所指的值 比 12 大
而且 mid 的值已经查过，
所以要把右边界拉到mid左边， 查找范围缩小到 2- 15 之间
mid = (0+3)/2 = 1
mid所指的值是 5 比 12 小
mid 的值已经查过
所以把左边界拉到mid的右边，范围缩小到 8-12 之间
mid = (2+3)/2 = 2 和left 重叠
8 比 12 小
因此左边界拉到 mid 值的 右边 left和right 重合，找到12
如果最终得到的值不是 12 ，经过判断 返回 -1 即可
代码
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
//初始化数组，范围变量
int arr[10] = { 2,5,8,12,15,17,19,22,25,32 };
int num = 0;
int lens = sizeof(arr) / sizeof(arr[0]);
scanf("%d", &num);
int left = 0;
int right = lens - 1;
// 查找过程
while (left < right)
{
int mid = left + (right - left) / 2;
if (arr[mid] < num)
{
left = mid + 1;
}
else if (arr[mid] > num)
{
right = mid - 1;
}
else
{
//由于下方判断使用 arr[right] 和 num比较，令 right = mid 统一判断
right = mid;
break;
}
}
//返回值，如果是函数用return就行
if(arr[right] == num)
{
printf("找到了坐标为:%d", right);
}
else
{
printf("没找到");
}
return 0;
}
二、折半查找变式
例子1
要求:
分析
看到非降序数组，可以考虑使用折半查找的方式实现
如果我们能够刚好找到 k 的左右边界，随后统计两者的距离就能得到k的个数
问题变成了，如何找到 k 数组的左右边界
左边界，可以使用 k-0.5 代替，因为整形数组，每次最少要加1，虽然找不到 k+0.5，但是最终的位置是指向左边界的
右边界,使用 k + 0.5代替，同理最后的位置就是右边界的地方
使用 右- 左 就是个数
代码
int bisearch(int *arr,int len,double k)
{
int left = 0;
int right = len -1;
while(left<=right)//注释1
{
int mid = left + (right-left)/2;
if(arr[mid]>k)
{
right = mid - 1;
}
else if(arr[mid]<k)
{
left = mid+1;
}
}
return left;
}
int GetNumberOfK(int* arr, int len, int k ) {
return bisearch(arr,len,k+0.5) - bisearch(arr,len,k-0.5);
}
部分问题的分析
注释1 ：一开始 我使用的是 left < right ,但是如果运用在 类似 [3,3,3,3]数组中找3，最大的指向返回 3，所以在相等的情况下，left 要先右偏移一个来满足数组定义和要求的差异
例子2
要求
旋转数组的最小数字
分析:
旋转数组可以看成有序数组的变式，在结合题目 O(logn) 要求，可以尝试使用折半查找
非降序，说明数据之间可以相等，可以举个例子测试如 [1,1,1,0,1,1]
旋转数组，说明有一部分有序，而且有序的那一部分最左数是最小值
如何找到有序部分是我们的重点
而有序数组的标志就是 left 的值 比right 小
如果数组是 [3,4,5,1,2]
mid = (0+4)/2 = 2,指向的是 5 , 因为 mid 的值比 right大，说明 mid 处在非有序的部分
非有序的部分 mid+1 指向的要么是非有序部分，要么是有序部分的最小值
所以 能够让 left = mid + 1;
随后 left 指向 1 ，right指向2 ,得到的 mid = (3+4)/2 = 3 指向 1,比 right 小，说明有序部分可以缩小
得到 right = mid - 1 ; 不是 right - 1 ,因为目标是要得到有序部分，mid - 1,的指向可能会跳到非有序部分
由于是非降序数组，因此元素之间可能会相等
如果 mid 和 right相等, 说明最小值在 mid - right 之间 或者是 left - mid 之间
而且不是 right 指向的值
说明 left - right 的范围可以缩小
并且mid 指向的值是和 right 指向的值比较 ，所以 right –
代码
{
int left = 0;
int right = rotateArrayLen - 1;
while(left<right)
{
int mid = left +(right - left)/2;
if(rotateArray[mid]>rotateArray[right])
{
left = mid+1;
}
else if(rotateArray[mid]<rotateArray[right])
{
right = mid;
}
else
{
right--;
}
}
return rotateArray[left];
}
总结
- 有序数组查找常使用折半查找，许多问题可以转换为查找问题
- 关注数值大小关系，找到特征
- 变式有 查找数，查找数的范围，寻找最小值等