二分查找法（函数binary

二分查找法（函数binary_search）

定义

复杂度

解析

函数binary_search

代码实现

运行结果

总结

定义

二分查找也叫折半查找，是一种高效率的查找方法，但是折半查找方法要求顺序存储结构，按关键字大小有序排列。

复杂度

时间复杂度即是while循环的次数。
二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2]，则找到x，算法中止；如果x<a[n/2]，则只要在数组a的左半部分继续搜索x；如果x>a[n/2]，则只要在数组a的右半部搜索x.

解析

函数binary_search

意思就是binary_search(数组，要找的数，数组长度)

代码实现

int binary_search(int arr[], int x, int sz) 
{int left = 0;int right = sz - 1;while (left <= right)//循环条件{int mid = (left + right) / 2;if (arr[mid] < x)left = mid + 1;else if (arr[mid] > x)right = mid - 1;elsereturn mid;//找到返回main函数；}return -1;//找不到退出}
int main()
{int arr[10] = { 1,2,3,4,5,6,7,8,9 };int x;scanf("%d",&x);//输入需要查找的数int sz = sizeof(arr) / sizeof(arr[0]);//数组大小int ret = binary_search(arr, x, sz);//函数if (ret == -1)printf("找不到\n");elseprintf("找到了，下标是：%d\n", ret);return 0;
}