二分查找(折半查找)详解python实现

二分查找

#简介:二分查找也叫折半查找,是一种效率很高的查找方法。给定一个整数x和整数集a1,a2,a3…an.
后者已经预先排序并在内存中,求使得整数集中某个元素等于所要查找的元素的索引。

算法要求:

1.必须采用顺序储存结构。
2.表中数据必须有序排列。

查找过程

这里以升序举例:
First:target= 52是我们要查找的目标,初始low是表中第一个元素的下标,high是表中最后一个元素的下标。mid= (low+high)/2表中中间元素的下标。
判断mid所指元素48和目标元素52的大小
二分查找(折半查找)详解python实现
Second:48比52小,所以使low指向原先mid的下一元素,此时mid也改变。
二分查找(折半查找)详解python实现
Third:69比52大,所以使指向mid的上一元素,此时mid所指向的是52,与目标元素相等,找到目标,返回此时的下标,查找成功。
二分查找(折半查找)详解python实现

效率高的原因

二分查找之所以快速,是因为它在匹配不成功的时候,每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快,而不像顺序查找那样,每次仅能排除一个元素。

完整代码:Python

class Solution:
    def find(self,nums,target):
        low = 0
        high = len(nums)
        while low <= high:                   #直到high < low后退出while循环
            mid = int((high + low) / 2)
            if nums[mid] < target:
                low = mid + 1                #小于目标值low索引+1
            if nums[mid] > target:
                high = mid - 1               #大于目标值high索引-1
            if nums[mid] == target:
                return mid                   #返回所查找元素的索引
        return -1                            #如果查找失败,返回-1
if __name__ == '__main__':
    s = Solution()
    nums = [1,2,3,3,5,6,7,8,8,10]
    print(nums)
    n = int(input('请输入你要查找的元素'))
    ln = s.find(nums,n)
    if ln != -1:
        print(f'查找元素第一次出现的索引为{ln}')
    else:
        print("没有此元素")
  2021.9.11.13:49



上一篇:mysql报Can't create/write to file '/tmp/ib0n3frL' (Errcode: 13 - Permission denied)


下一篇:52:代码审计-PHP项目类RCE及文件包含下载删除