文章目录

前言

当我们需要在一堆有序的数组中（二分查找只支持有序数组）找到某个元素的位置，即下标的时候，最常见的是遍历的方法（暴力求解法），一个个核对，不相等就跳到下一个，但是这种方法要浪费很多时间。这时候，我们就需要用到折半（二分）查找算法啦。

一、思路

那什么是折半（二分）查找算法呢？

我们先来看一个情景—猜数字游戏，数字的范围在1-100之间，我让你猜某个数字，那么聪明的你第一时间肯定会猜50，然后我告诉你猜小了，然后你接下来猜肯定在51-100之间猜75，我又告诉你猜大了，然后你继续像这样才直到猜出正确的数字，其实在这个猜数字的过程中，你用到的就是折半查找算法，那么我们需要用相同的逻辑用代码实现这个折半查找算法。

图解

开始时，left=0,right=9(为数组元素下标)，现在你要折半找到中间元素，所以mid(middle是中间的意思)=(left+right)/2=4,下标为4的元素是5,5比7小，即arr[mid]<k,这时候你是不是就要从6-10中寻找呢？，所以这时候，left=mid+1,right则不变，因为没找到你要的元素，所以你继续折半查找，这时候mid=7,下标为7的元素是8，比k大，所以则时候范围缩小到6和7，下标分别为5,6，mid=5,arr[mid]=6,比k小，所以mid+1，这时候就找到k了，及时跳出循环。注意要用循环来实现，条件是left<=right.

二、代码的实现

#include<stdio.h>int main(){//数组的下标从0开始int arr[10] = {1,2,3,4,5,6,7,8,9,10 };int k = 7;//利用sizeof函数计算数组元素个数int sz = sizeof(arr) / sizeof(arr[0]);//10int left = 0;int right = sz - 1;//元素10的下标为9//循环的条件while (left <= right){int mid = left +(right - left)/2;//防止溢出//int mid=(left+right)/2;if (arr[mid] < k){left = mid + 1;}else if (arr[mid] > k){right = mid - 1;}else{printf("找到k了，下标为：%d\n", mid);break;//找打元素之和就赶紧退出循环，不然会陷入死循环的！}}if (left > right){printf("找不到\n");}return 0;}

如果觉得《【C语言】详解：折半查找（二分查找算法）》对你有帮助，请点赞、收藏，并留下你的观点哦！