二分法思想找到有序数组中的数字

上山打老虎

在一个有序数组中，我们可以通过依次查找的方式找到想要的那个数字的下标，但这样费时费力。可以采用二分法，这样可以使程序更快的运行起来，方便使用。
下面分别介绍使用函数和不使用函数的方法：
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[mid] > k)
{
right = mid-1;  //千万不能写成right=arr[mid]-1,会陷入死循环，后面也是一样
}
else if (arr[mid] < k)
{
left = mid+1;
}
else if (arr[mid] = 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[0]); //计算数组中数字的个数，这一步在函数中无法实现，只能写在函数外面
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[0]);
int right = sz - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] < k)
{
left = mid + 1;
}
else if (arr[mid]>k)
{
right = mid - 1;
}
else
{
printf("找到了，下标是%d\n", mid);
break;
}
}
if (left > right)
printf("找不到，不存在\n");
return 0;
}