四川高速公路建设开发集团有限公司网站山东seo

一.什么是二分查找

在⼀个升序的数组中查找制定的数字n，很容易想到的⽅法就是遍历数组，但是这种⽅法效率⽐较低，
⽐如我买了⼀双鞋，你好奇问我多少钱，我说不超过300元。你还是好奇，你想知道到底多少，我就让
你猜，你会怎么猜？你会1，2，3，4…这样猜吗？显然很慢；⼀般你都会猜中间数字，⽐如：150，然
后看⼤了还是⼩了，这就是⼆分查找，也叫折半查找。

二.代码实现

int main()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };int left = 0;int right = sizeof(arr) / sizeof(arr[0]) - 1;int key = 0;scanf("%d", &key);int mid = 0;int find = 0;while (left <= right){mid = (left + right) / 2;if (arr[mid] > key){right = mid - 1;}else if (arr[mid] < key){left = mid + 1;}else{find = 1;break;}}if (1 == find)printf("找到了,下标是%d\n", mid);elseprintf("找不到\n");
}

运行结果：