1.折半查找的定义：

在计算机中，折半查找，也称二分搜索。它是一种在有序数组中查找某一特定元素的搜索算法。

2.折半查找的实现原理：        

        搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半 。

以下是折半查找和顺序遍历的算法实实现动态图

3.折半查找算法优点：

折半查找法的优点是比较次数少，查找速度快，平均性能好；

其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

4.代码实现：

# include<stdio.h>
# include<string.h>
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//下标：0，1，2，3，4，5，6，7，8，9
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){
right = mid - 1;
}
 
else if (arr[mid] < k){
    left = mid + 1;
}
 
else{
printf("找到了：%d\n", mid);
break;
}
    }
 
if (left > right)//情况四：找不到
{
printf("找不到了\n");
}
return 0;
}

        代码讲解：       

         1.通过建立左下标left与右下标right组成一个完整的范围。

         2.创建关键查找数k，作为范围内要被查找的数字。

         3. int mid = (left + right) / 2;这句是折半查找的核心语句，作用就是计算两边元素之和除2（为中间元素）与要查找的元素做对比，进而确定查找数的范围。

         4.if (arr[mid] > k)表示情况一：求出的中间数若>要查找的数，就将右下标移位到mid的左边一位，直接消去其中一半，之后再求出左下标与更新的右下标的中间元素，更新出新的范围，再与要找元素重新进行对比。

        5.else if (arr[mid] < k)表示情况二：求出的中间数若 <要查找的数，就将左下标移位到mid的右边一位，直接消去其中一半，之后再求出左下标与更新的右下标的中间元素，更新出新的范围，再与要找元素重新进行对比。

        6.else表示情况三：若恰好相等，则直接跳出循环，printf打印输出。

        7.if (left > right)表示情况四：找不到。

函数版：优化了一下

#include<stdio.h>
#include<String.h>
int test(int arr[], int sz, int k) {
int left = 0;
int right = sz - 1;
while (left <= right)
{
int mid = (left + right) / 2;
 
if (arr[mid] > k)
right = mid - 1;
 
else if (arr[mid] < k)
left = mid + 1;
 
else
return mid;
}
if (left > right)//情况四：找不到
return -1;
        }
 
int main() {
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//下标：0，1，2，3，4，5，6，7，8，9
int k = 0;
scanf("%d", &k);
int sz = sizeof(arr) / sizeof(arr[0]);
int ret = test(arr, sz, k);
if (ret == -1) {
printf("未找到该元素，该元素不存在！\n");
}
else {
printf("找到了，该元素下标处于：%d的位置", ret);
}
return 0;
}