二分法查找：在数据有一定顺序的情况下，且遍历无法快速查找时使用
需根据上次查找范围的中间值，来对比指定值 确定下一次查找范围
每查找一次，下次查找范围缩小到上次查找范围的二分之一，故二分法
可以快速排除大部分无用数据，减少一定的时间复杂度
给定一个有序的 整型数组
int arr[20] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 };
需要 找到其中某个数 在数组中的位置的下标
例如 需要找到 13 所在位置的下标
int num = 0;
scanf("%d", &num); //此语句输入 13 后 num = 13
二分法需要知道 数组中元素个数
int sz = sizeof(arr) / sizeof(arr[0]); //sizeof() 求类型长度 //sizeof(arr)（数组总长度） / sizeof(arr[0])（数组中单个元素长度） == 数组中元素个数
确定数组 首、末元素下标
int left = 0; //首元素 为 左 下标为 0 int right = sz - 1; //末元素 为 右 下标为 元素个数 - 1
确定数组 中间元素 下标
int mid = (left + right) / 2; //数组中间元素 下标
用中间元素 对比 指定值 的大小 判断下次查找范围
if (arr[mid] < num)
left = mid + 1; //指定数 大于 数组中间值 则 下次查找时 查找范围左下标变为mid + 1
else if (arr[mid] > num)
right = mid - 1; //指定数 小于 数组中间值 则 下次查找时 查找范围右下标变为mid - 1
else
{
printf("n找到了,指定数下标为 %d n ", mid );
break; //指定数 等于 数组中间值 则 跳出循环 查找成功
}
上为 一次 二分查找的过程，未找到之前，需要循环查找 知道 找到
利用二分法 查找时，找到之前 left < right ，找到时 left == right
所以 循环条件应为 (left <= right)
补上循环条件，查找过程部分的 代码为：
//查找范围恒为 arr[left] ~~ arr[rihgt] 之间
//在查找过程中 left 和 right 可能在不停变化 即查找范围在不停变化
//直到 left == right 时 代表查找成功
//此时 arr[left] == arr[rihgt] == arr[mid] == 查找值
while (left <= right) //判断元素的被找到的标志为 元素左右下标相等
{
int mid = (left + right) / 2; //求数组中间元素 下标
if (arr[mid] < num)
left = mid + 1; //指定数 大于 中间值 查找范围左下标变为mid + 1 因此给定数组递增 下次查找向右继续
else if (arr[mid] > num)
right = mid - 1; //指定数 小于 中间值 查找范围右下标变为mid - 1 因此给定数组递增 下次查找向左继续
else
{
printf("n找到了,指定数下标为 %d n ", mid );
break; //指定数 等于 数组中间值 则 跳出循环 查找成功
}
}
第一次写博客，可能写的不好，请多关照！！！
下面是二分法查找指定数的全部代码：
#define _CRT_SECURE_NO_WARNINGS #include//二分法初接触：在有序数组中 查找指定值 int main() { int arr[20] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 }; int num = 0; printf("请输入要查找的数：>"); scanf("%d", &num); int sz = sizeof(arr) / sizeof(arr[0]); //sizeof(arr)（数组总长度） / sizeof(arr[0])（数组中单个元素长度） == 数组中元素个数 int left = 0; //首元素 为 左 下标为 0 int right = sz - 1; //末元素 为 右 下标为 元素个数 - 1 //查找范围恒为 arr[left] ~~ arr[rihgt] 之间 //在查找过程中 left 和 right 可能在不停变化 即查找范围在不停变化 //直到 left == right 时 代表查找成功 //此时 arr[left] == arr[rihgt] == arr[mid] == 查找值 while (left <= right) { int mid = (left + right) / 2; //求数组中间元素 下标 if (arr[mid] < num) left = mid + 1; //指定数 大于 中间值 查找范围左下标变为mid + 1 因此给定数组递增 下次查找向右继续 else if (arr[mid] > num) right = mid - 1; //指定数 小于 中间值 查找范围左下标变为mid - 1 因此给定数组递增 下次查找向左继续 else { printf("n找到了,指定数下标为 %d n ", mid ); break; //指定数 等于 数组中间值 则 跳出循环 查找成功 } } if (left < right) printf("数组中没有 指定数"); //查找范围的左下标 大于右下标 无法查找 即数组中没有 指定数 return 0; }
