有序数组中查找具体数字n（二分查找）
有序数组中查找具体数字n（二分查找）
题目
在一个有序的数组中查找具体的某个数字n，编写功能：在v[0]<=v[1]<…
思路（一）
我们先定义一个有序的数组arr，再设置数组中的一个数字k为我们所寻找的值，当数字与算法结果匹配时，打印“找到了，下标为–”，若该数字在数组中未查找到，则打印“找不到”。 因为该数组是有序的，我们可以利用一个循环结构，当i
在有序的数组中查找具体的某个数 元素个数 sz =（数组空间总大小）sizeof（arr）/ sizeof（arr[0]） 实现代码如下：
//在一个有序的数组中查找具体的某个数字n，编写功能：在v[0]<=v[1]<...
#include
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int k = 7;
//写一个代码在arr数组中（有序的）中找到7.
int i = 0;
int sz = sizeof(arr) / sizeof(arr[0]);
for (i = 0; i < sz; i++)
{
if (k == arr[i])
{
printf("找到了,下标是%d\n",i);
break;
}
}
if (i == sz)
printf("找不到\n");
return 0;
}运行结果如下：
思路（二）
上述算法并不够高效，在数组有序的情况下，找数字可用更高效的方法
折半查找法或二分查找法 如果数组中有n个数字，那么逐个查找最坏将查找n次，当n很大时，计算机运算量将更大，而二分查找法只需查找
折半查找法 或二分查找法
每次与数组中间坐标（mid=(left+right)/2）对应的数字比较，每次缩小一半的范围。
设置数组左下标left=0，右下标right=sz-1（元素个数-1） 当（left<=right）在循环里每次将arr[mid]与k进行比较
1.arr[mid] 中间元素小于要查找的数，说明要查找的数在中间数的右边，所以中间数左边的内容就可以舍弃了，同时left=mid+1，在新的范围里继续查找。
2.arr[mid]>k 中间元素大于要查找的数，说明要查找的数在中间数的左边，所以中间数右边的内容就可以舍弃了，同时right=mid-1，在新的范围里继续查找。
3.arr[mid]=k 此时k被找到，mid为其下标.
当（left>right）跳出循环 在当前数组中未能查找到该数字k，打印未找到。
实现代码如下：
//该算法不够高效，在数组有序的情况下，找数字可用更高效的方法
//折半查找法或二分查找法
//如果数组中有2^32个数，一般方法最坏要查找2^32次，而二分查找法只需查找log2n次
//折半查找法 或二分查找法
#include
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int sz = sizeof(arr) / sizeof(arr[0]);
int left = 0;
int right = sz - 1;
int k = 7;
int mid = 0;
while (left <= right)
{
mid = (right + left) / 2;
if (k<arr[mid])
{
right = mid - 1;
}
else if (k>arr[mid])
{
left = mid + 1;
}
else
{
printf("找到了，下标是%d\n", mid);
break;
}
}
if (left > right)
printf("找不到\n");
return 0;
}实现结果如下：
将代码封装成函数形式如下：
#include
int binary_search(int arr[], int k, int sz)
{
int left = 0;
int right = sz - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (k<arr[mid])
{
right = mid - 1;
}
else if (k>arr[mid])
{
left = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
int main()
{
//有序的
int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int k = 100;
int sz = sizeof(arr) / sizeof(arr[0]);
//二分查找的
//找到了，返回下标
//找不到，返回 -1
int ret = binary_search(arr, k, sz);
if (ret == -1)
{
printf("找不到\n");
}
else
{
printf("找到了，下标是：%d\n", ret);
}
return 0;
}注意：一定是在有序的数组中才可以运用二分查找法
谢谢欣赏！ ^ __ ^