二分法思想找到有序数组中的数字
在一个有序数组中，我们可以通过依次查找的方式找到想要的那个数字的下标，但这样费时费力。可以采用二分法，这样可以使程序更快的运行起来，方便使用。下面分别介绍使用函数和不使用函数的方法：
1.使用函数
int binary_search(int arr[], int k, int sz)//arr是数组，后面必须有[]
{
int left = 0;
int right = sz - 1;//下标从0开始，所以下标的最大值比数组中数字的个数少1
while (left <= right)
{
int mid = (left + right) / 2;
if (arr > k)
{
right = mid-1;//千万不能写成right=arr-1,会陷入死循环，后面也是一样
}
else if (arr < k)
{
left = mid+1;
}
else if (arr = k)
{
return mid;
}
}
return -1;
}
//函数需要有可重复性，不要随便在函数中执行打印命令
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int a = 8; //查找数字8的下标
int sz = sizeof(arr) / sizeof(arr); //计算数组中数字的个数，这一步在函数中无法实现，只能写在函数外面
int ret=binary_search(arr, a, sz);
if (ret!=-1)
printf("该数下标为：%d\n", ret);
if (ret == -1)
printf("找不到该数\n");
return 0;
}2.不使用函数
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9,10 };
int k = 8;
int left = 0;
int sz = sizeof(arr) / sizeof(arr);
int right = sz - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr < k)
{
left = mid + 1;
}
else if (arr>k)
{
right = mid - 1;
}
else
{
printf("找到了，下标是%d\n", mid);
break;
}
}
if (left > right)
printf("找不到，不存在\n");
return 0;
}
文档来源：51CTO技术博客https://blog.51cto.com/u_15312867/3308327
页:
[1]