数据结构——二分查找

1、二分查找的定义

​ 二分查找也称折半查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

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

算法要求：

​ 1.必须采用顺序存储结构

​ 2.必须按关键字大小有序排列

二分查找的图示为：

2、二分查找算法代码实现

​

int BinarySearch(List Tb1, ElemType K){
    ElemType left, right, mid;        //定义元素指标
    int NoFound = -1;        //定义元素K没有被找到的返回结果
    left = -1;        //定义初始指标值
    right = Tb1->length;
    while(left <= right){
        mid = (left + right)/2;
        if(K < Tb1->array[mid])        //如果K在array[mid]的左侧
            right = mid - 1;
        else if(K > Tb1->array[mid])        //如果K在array[mid]的右侧
            left = mid + 1;
        else
            return mid;        //如果K等于array[mid]
    }
    return NoFound;        //没有找到K
}

3、二分查找的优缺点

二分查找的算法时间复杂度为O(logN)

优点：比较次数少，查找速度快，平均性能好

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