6.3 折半查找

damone大约 1 分钟

6.3 折半查找

6.3.1 折半查找的定义

折半查找，又叫二分查找。仅适用于有序的顺序表。

6.3.2 折半查找的实现

算法思想：每次从中间分，判断自己是哪一半

普通代码：

//查找表的数据结构（动态分配的顺序表）
typedef struct{
    ElemType *elem;      //指向“动态”分配的数组的指针
    int TableLen;        //查找表的当前长度
}SSTable;
//折半查找
int Binary_Search(SSTable L, ElemType key){
    int low =0, high = L.TableLen-1, mid;
    while(low <= high){
        mid = (low + high)/2;           //取中间值
        if(L.elem[mid] == key){
            return mid;                 //查找成功，则返回所在位置
        }else if(L.elem[mid] > key){
            high = mid - 1;             //从前半部分继续查
        }else{
            low = mid + 1;              //从后半部分继续查
        }  
    }
    return -1;                          //查找失败，返回-1
}