数据结构折半查找法（算法思想和源代码）

水深无声 2022-06-07 11:36 119阅读 0赞

## Ⅰ ）算法思想 ##

首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。  
     重复以上步骤，直到找到满足条件的结果为止，若找不到，则返回失败。

## Ⅱ）源代码 ##

#include<stdio.h>
     
    #define MaxSize 20
    typedef struct
    {
        int key;
    }RecordType;
     
    typedef struct
    {
        int length;
        RecordType r[MaxSize + 1];
    }RecordList;
     
    int BinSearch(RecordList l, int key)
    {
        int low = 1;
        int high = l.length;             //置区间初值
        int mid;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (key == l.r[mid].key)
            {
                return mid;              //如果要查找值key == l.r[mid].key返回mid下标
            }
            else if (key < l.r[mid].key) 
            {
                high = mid - 1;          //未找到，把high往mid前移一位在前半区间查找
            }
            else
            {
                low = mid + 1;          //在后半区间查找
            }
        }
        return 0;
    }
    int main()
    {
        RecordList L = { 10, 0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100};  //初始化线性表
        printf("%d\n", BinSearch(L, 30));       //查找30所在的下标
        return 0;
    }