临汾家教:数据结构和算法:Python实现二分查找(Binary_search)

admin 10个月前 (05-06) 科技 72 2

皇冠体育APP

皇冠体育APP是一个开放皇冠代理APP下载、皇冠会员APP下载、皇冠线路APP下载、皇冠登录APP下载的平台,皇冠体育APP上最新登录线路、新2皇冠网址更新最快,皇冠体育APP开放皇冠会员注册、皇冠代理开户等业务。

,

在一个列表当中我们可以进行线性查找也可以进行二分查找,即通过不同的方法找到我们想要的数字,线性查找即按照数字从列表里一个一个从左向右查找,找到之后程序停下。而二分查找的效率往往会比线性查找更高。

一.二分查找的步骤

二分查找的步骤首先是将列表进行升序或者降序排列,否则无法进行数字的比较,也就无法进行二分查找。然后找到一个列表的中间数值(mid),如果列表当中的数字和为基数,则为最中间的那个数。如果为偶数,则为最中间的那两个数的左边那一个,比如说我们有一个列表,[1,2,3,4,5,6],列表当中的数字为偶数个,那么mid则是3。找到mid之后,再和我们需要查找的数字进行比较,如果比我们需要查找的数字要小,那么就让low=mid+1,即在Mid的右边一个,如果比我们需要的数字要大,则让high=mid—1,在high的左边一个,利用夹逼法直到mid等于var的时候这个时候在返回mid的值,这个值就是我们数字所在的顺序数,在列表当中的order或称index(索引)。我们下面一张图来表示二分查找的步骤,下面是举了一个最为简单的列子,数字的个数仅为4个,且为1,2,3,4。

 

 假设我们想要找的数字为3的index,因此首先在第一次循环当中,1=low,4=high,mid=2,我们令var=3,也就是我们想要找的数为var,发现这个数的数值是比mid的数值更大的,因此low=mid+1,此时mid所代表的数值变成了3。紧接着我们进行下一次循环,我们发现var和mid是相等的,因此返回mid的数值(并非mid所对应在列表当中的数值,而是mid自己的值),这样就可以得到var的索引值了!实现的程序如下:

# 首先咱们来看一个线性查找,这个的效率比较低
li = [1,2,3,4,0,4,2,3]

# print(6 in li)# 这个就是线性查找,看6是否在里面
# print(li.index(6))# 看6在第几个index


li.sort()
print("进行排序之后的列表为:{}".format(li))


def bin_search(li, var):
    low = 0
    high = len(li) - 1
    while low<=high:# 这里不能够使用while true!!不然输入一个不存在的值的话就会导致mid做了加减法后low比high大或者high比Low小,失去了比较的意义
        mid = (low + high) // 2
        if li[mid] == var:
            return mid
        elif li[mid] < var:
            low = mid + 1
        else:# li[mid] > var
            high = mid - 1
    return -1


# 二分查找的时间复杂度为log(n)
if __name__ == "__main__":
    print(bin_search(li, 3))

 

在程序当中需要注意的是循环while的判断条件是low<=high,因为如果在输入的值var不属于列表的情况下,运算到最后low就会大于high,这种情况下是应该直接返回-1的,而不是继续运算到无穷无尽。在这个程序当中我们设定了列表li,并通过定义二分查找函数来执行二分查找的过程。程序也很通俗易懂,和之前我们讲过的二分查找的步骤是一样的,下面我们来看一个利用二分查找的例题:

二.例题

这个例题节选自悉尼大学“Python编程”这门课的每周同步编程练习,题目是这样的:

输入一个序列,然后让整个序列变成一个有序的列表,最后找到数字8在这个列表当中的位置,我们可以使用二分查找来做这道题目,标准的Example如下:

 

 

 

 

 

 

现在我们使用二分查找算法来实现这个问题,首先是输入的字符串用input()函数来进行接收,但是接收之后的数字是字符串,我们需要使用split()函数将其每一个元素通过间隔开,由于使用了split()函数,因此就会自己动返回一个列表,不过里面每一个数字也还是string型,我们再利用一个for循环将其改变为int型,再重新灌入一个列表当中,形成interger型的列表,也就是我们第二个的输出结果,最后运用咱们刚才的二分查找法,得到数字8的index值,程序如下:

def binary_search(list, var):
    low = 0
    high = len(list)-1
    while low <= high:
        mid = (low+high)//2
        if list[mid] == var:
            return mid
        elif list[mid] < var:
            low=mid+1
        else:
            high=mid-1
    return -1

a = input("Enter some integers:")
a = a.split(",")
print(a)
ls = []
for i in a:
    b = int(i)
    ls.append(b)

print("我们得到的数组是:{}".format(ls))
# 将列表进行升序排列,这样才可以使用二分查找算法
ls.sort()
print(ls)


if __name__ == "__main__":
    print(binary_search(ls,5))

输出结果如下:

E:\conda\python.exe F:/computer/datast/T4Q6P4.py
Enter some integers:23,4456,234,67,5
['23', '4456', '234', '67', '5']
我们得到的数组是:[23, 4456, 234, 67, 5]
[5, 23, 67, 234, 4456]
0

今天的教程就到这里了!希望你看了之后会有收获!

 

Sunbet声明:该文看法仅代表作者自己,与本平台无关。转载请注明:临汾家教:数据结构和算法:Python实现二分查找(Binary_search)

网友评论

  • (*)

最新评论

  • 申博代理app下载 2020-04-21 00:55:44 回复

    Sunbet 申博Sunbet 申博在2019年立足亚太,寻求业界翘楚合作运营线上游戏平台。Sunbet www.jxadap.com自与江西安达安全评价咨询有限责任公司合作以来,优势互补、资源整合、在未来一定会用心运营,赢得每位代理、会员的口碑。不知道说啥,给大家拜年

    1

文章归档

站点信息

  • 文章总数:823
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1274
  • 评论总数:542
  • 浏览总数:36302