20180312折半查找

2019独角兽企业重金招聘Python工程师标准>>>

前置知识

• 需要将待查找的列表按关键字大小有序排序。

本期内容

名词解释

• 查找过程
  • 关键字与mid=(low+high)/2进行比较
  • 大于：low=mid+1
  • 小于：high=mid-1

实现

• 非递归的方式
  • 时间复杂度是**O(lon_2n)

int BiSearch(int r[], int n, int iKey)
{
    int low=0,high=n-1;
    while(low <= high)
    {
        mid=(low+high-1)/2;
        if(r[mid]<iKey)
            low = mid+1;
        else if(r[mid]>iKey)
            high = mid-1;
        else 
            return mid;
    }
    return -1;
}

• 递归的方式

int IterBiSearch(int arr[], const int num, int begin,int last)
{
    int mid = -1;
    mid = (beign+last)/2;
    if(num=arr[mid])
    {
        return mid;
    }
    else if(num<arr[mid])
    {
        return IterBiSearch(arr, num,begin,mid-1);
    }
    else if(num>arr[mid])
    {
        return IterBiSearch(arr, num,mid+1,last);
    }
    return -1;
}

总体评价

• 优点是比较次数少，查找速度快，平均性能好。
• 缺点要求待查表为有序表，且插入删除困难。
• 适用于不经常变动且查找频繁的有序列表。

代码学习

• zheban.c

履历

• 20180312整理完，但以下两点没弄清楚
  • 用递归的方式实现
  • 时间复杂度的计算
• 20180313增加递归的方式实现

转载于:https://my.oschina.net/wolflion/blog/1633560