以下可以正确获取结果集的有_为了有序表进行二分查找「建议收藏」

以下可以正确获取结果集的有_为了有序表进行二分查找「建议收藏」defbisearch(l,e,lo,hi):whilelohi:mi=(lo+hi)//2ifel[mi]:lo=mi+1else:hi=mireturnhi注:(1)不同于寻找等于某值的情况(

以下可以正确获取结果集的有_为了有序表进行二分查找「建议收藏」"

1. 不小于某数的第一个元素

def bisearch(l, e, lo, hi):
    while lo < hi:
        mi = (lo + hi)//2
        if e > l[mi]: lo = mi + 1
        else: hi = mi
    return hi

注:

  • (1)不同于寻找等于某值的情况(且找到即可,不要求第一个),体现在代码中,就是判断逻辑;

2. 不大于某数的最后一个元素

def binsearch(l, e, lo, hi):
    while lo < hi-1:
        mi = (lo + hi)//2
        if e >= l[mi]: lo = mi
        else: hi = mi
    return lo

注:另外的两种情况,

  • 1) 不大于某数的第一个元素 ⇒ 既然有序,左端遍历即可;
  • 2) 不小于某数的最后一个元素 ⇒ 既然有序,从尾端开始遍历即可;

没有实质的意义。

3. 传统的二分支和三分支的版本(判等)

# 三分支
def binsearch(l, e, lo, hi):
    while lo < hi:
        mi = (lo + hi)//2
        if l[mi] > e: hi = mi
        elif: l[mi] < e: lo = mi + 1
        else: return mi
    return lo if A[lo] == e else -1

# 二分支
def binsearch(l, e, lo, hi):
    while lo < hi - 1:
        mi = (lo + hi)/2
        if e < l[mi]: hi = mi
        else: lo = mi
    return lo if A[lo] == e else -1

请注意,以上的两个版本(三分支和二分支):

  • 三分支:直接返回居中的符合条件的即可,不考虑相对顺序
  • 二分支:其实返回的是最后一个等于某值元素
l = [4, 4, 4, 4, 4]
binsearch(l, 4, 0, 5)
            # 对于三分支而言,返回的是 2
            # 对于二分支而言,返回的是 4

4. 返回值等于某值的第一个元素(最后一个元素)

4.1 值等于某值的第一个元素

其实可以泛化地理解为值不小于某值的第一个元素,也就是本文开篇的第一个代码段:

def binsearch(l, e, lo, hi):
    while lo < hi:
        mi = (lo + hi)//2
        if e > l[mi]: lo = mi + 1
        else: hi = mi
    return hi

4.2 值等于某值的最后一个元素

其实就是 Part3 中的二分支版本;
也即:

def binsearch(l, e, lo, hi):
    while lo < hi:
        mi = (lo + hi)//2
        if e < l[mi]: hi = mi
        else: lo = mi
    return lo

今天的文章以下可以正确获取结果集的有_为了有序表进行二分查找「建议收藏」分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/86781.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注