**

二分查找（折半查找）总结

**

---

一、基本概念

二分查找也叫折半查找，是一种效率比较高的查找方法。但是使用它有个前提：必须是采用顺序存储的线性表，表中按关键字有序排列，一般情况为按数值从小到大排列。
折半查找的过程为：

1. 从表的中间记录开始，将查找值与其比较，如果相等则查找结束
2. 如果中间值小于查找值，则查找值一定在表的后一半区间里，于是将左值设置为中间位置的下一个
3. 如果中间值大于查找值，则查找值一定在表的前一半区间里，于是将右值设置为中间位置的前一个
4. 设置完成后，继续从新区间的中间值开始比较，即继续第一步的内容直至查找完成
5. 如果没有查找到，则返回-1

二、编写代码

1.二分查找

int BinarySearch(int arr[],int len,int key)
{
    
    int left,mid,right;
    left=0;
    right=len;

    while(left<=right)
    {
    
        mid=(left+right)/2;

        if(arr[mid]<key) left=mid+1;
        else if(arr[mid]>key) right=mid-1;
        else break;
    }

    if(left<=right) return mid;
    else return -1;
}

2.测试代码

#include <stdio.h>

int BinarySearch(int arr[],int len,int key)
{
    
    int left,mid,right;
    left=0;
    right=len;

    while(left<=right)
    {
    
        mid=(left+right)/2;

        if(arr[mid]<key) left=mid+1;
        else if(arr[mid]>key) right=mid-1;
        else break;
    }

    if(left<=right) return mid;
    else return -1;
}

int main()
{
    
    int testArr[]={
    3,6,9,16,21,29,56,67,89,99};
    int len=sizeof(testArr)/sizeof(testArr[0])-1;

    printf("%d\n",BinarySearch(testArr,len,67));//查找到
    printf("%d",BinarySearch(testArr,len,0));//未查找到

    return 0;
}

三、输出结果

可以看到：

• 查找到结果时，输出数组下标
• 未查找到时，输出-1

---

四、总结评价

二分查找的过程也可以用二叉树来描述，树中每个结点对应表中一个数据，但是结点不是记录的关键字，而是记录在表中的数组下标。由此得到的二叉树称为二分查找的判定树。

二分查找的优缺点：

• 比较次数少，查找效率高
• 只能适用于顺序存储结构的线性表

二分查找不适用于数据元素经常变动的线性表

有问题欢迎各位大佬指出
算法系列将持续更新，欢迎关注，一起学习