python算法与数据结构-常用查找算法一(37)

一、什么是查找

查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
查找表（Search Table）：由同一类型的数据元素（或记录）构成的集合
关键字（Key）：数据元素中某个数据项的值，又称为键值。
主键（Primary Key）：可唯一地标识某个数据元素或记录的关键字。

　　搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的，因为该项目是否存在。搜索的几种常见方法：顺序查找、二分法查找、二叉树查找、哈希查找。

二、无序表查找

也就是数据不排序的线性查找，遍历数据元素。
算法分析：最好情况是在第一个位置就找到了，此为O(1)；最坏情况在最后一个位置才找到，此为O(n)；所以平均查找次数为(n+1)/2。最终时间复杂度为O(n)

# 最基础的遍历无序列表的查找算法

# 时间复杂度O(n)

def sequential_search(lis, key):

    length = len(lis)

    for i in range(length):

        if lis[i] == key:

            return i

    else:

        return False

if __name__ == '__main__':

    LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]

    result = sequential_search(LIST, 123)

    print(result)

三、二分查找(Binary Search)

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

算法核心：在查找表中不断取中间元素与查找值进行比较，以二分之一的倍率进行表范围的缩小。

1、二分查找的python代码实现

def binary_search(lis, key):

    low = 0

    high = len(lis) - 1

    time = 0

    while low < high:

        time += 1

        mid = int((low + high) / 2)

        if key < lis[mid]:

            high = mid - 1

        elif key > lis[mid]:

            low = mid + 1

        else:

            # 打印折半的次数

            print("times: %s" % time)

            return mid

    print("times: %s" % time)

    return False

if __name__ == '__main__':

    LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]

    result = binary_search(LIST, 1)

    print(result)

运行结果为：

查找次数为: 3

下表为：0

2、二分查找的C语言代码实现

//  main.m

//  二分查找

//  Created by 侯垒 on 2019/7/1.

//  Copyright © 2019 可爱的侯老师. All rights reserved.

# include <stdio.h>

int binary_search(int array[],int key,int len)

{

    int low = ;

    int high = len-;

    int time = ;

    while (low<high)

    {

        time++;

        int mid = (int)(low+high)/;

        if (key<array[mid])

        {

            high = mid-;

        }

        else if(key>array[mid])

        {

            low = mid+;

        }

        else

        {

            // 打印这本的次数

            printf("查询次数 = %d\n",time);

            return mid;

        }

    }

    printf("查询次数 = %d\n",time);

    return -;

}

int main(int argc, const char * argv[])

{

    int array[] = {, , , , , , , , , , };

    int index = binary_search(array, , );

    printf("下标是 = %d\n",index);

    return ;

}

运行结果为：

查询次数 = 

下标是 =

四、插值查找

　　在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？

　　打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。

　　同样的，比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5，我们自然会考虑从数组下标较小的开始查找。

　　经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：

　　mid=(low+high)/2, 即mid=low+1/2*(high-low);

　　通过类比，我们可以将查找的点改进为如下：

　　mid=low+(key-list[low])/(list[high]-list[low])*(high-low)，

　　也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。

　　基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。

　　注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

　　复杂度分析：查找成功或者失败的时间复杂度均为O(log(n))。

1、插值查找的python代码实现

def chazhi_search(lis, key):

    low = 0

    high = len(lis) - 1

    time = 0

    while low < high:

        time += 1

        # 计算mid值是插值算法的核心代码

        mid = low + int((key - lis[low])/(lis[high] - lis[low]) * (high - low))

        print("mid=%s, low=%s, high=%s" % (mid, low, high))

        if key < lis[mid]:

            high = mid - 1

        elif key > lis[mid]:

            low = mid + 1

        else:

            # 打印查找的次数

            print("查询次数: %s" % time)

            return mid

    print("times: %s" % time)

    return False

if __name__ == '__main__':

    LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]

    index = chazhi_search(LIST, 1)

    print("下标为：%s"%index)

运行结果为：

mid=, low=, high=

查询次数:

下标为：

2、插值查找的C语言代码实现

//  main.m

//  插值查找

//  Created by 侯垒 on 2019/7/1.

//  Copyright © 2019 可爱的侯老师. All rights reserved.

#include<stdio.h>

int chazhi_search(int array[],int key,int len)

{

    int low = ;

    int high = len-;

    int time = ;

    while (low<high)

    {

        time++;

        // 计算mid值是插值算法的核心代码

        int mid = low + (int)((key - array[low])/(array[high]-array[low])*(high-low));

        printf("mid=%d, low=%d, high=%d\n",mid, low, high);

        if (key<array[mid])

        {

            high = mid-;

        }

        else if (key>array[mid])

        {

            low = mid+;

        }

        else

        {

            // 打印查找的次数

            printf("查询次数:%d\n",time);

            return mid;

        }

    }

    printf("查询次数:%d\n",time);

    return -;

}

int main(int argc, const char * argv[]) {

    int arr[] = {, , , , , , , , , , };

    int index = chazhi_search(arr, , );

    printf("下标为：%d\n",index);

    return ;

}

运行结果为：

mid=, low=, high=

查询次数:

下标为：

巴特西

python算法与数据结构-常用查找算法一(37)

一、什么是查找

二、无序表查找

三、二分查找(Binary Search)

四、插值查找

最新文章

热门文章