python - 我想进行二进制搜索，但结果有误

Question

我想对列表进行二分查找，但即使我检查了列表中的数字，结果仍显示“false”。

def clist(a):

    l = [2,6,5,9,7,1,4,8,3]
    newl = sorted(l)
    check = int(1+len(newl)/2)

    if newl[check] == a:
        return True

    if check > a:
        for x in newl[:check]:
            if x == a:
                return True
            return False

    if check < a:
        for x in newl[check::]:
            if x == a:
                return True
            return False

print(clist(7))

Answer 1

你可以这样写你的脚本:

1. 取列表中间的元素
2. 如果这是您需要的，请归还
3. 如果你的 needle 比中间的 gt，则在列表的剩余右侧调用 bsearch
4. 否则用左侧调用bsearch

def bsearch(needle, haystack):
    l = len(haystack)
    half = int(l / 2)
    element = haystack[half];

    if element == needle:
        return element

    if needle <= element:
        return bsearch(needle, haystack[0:half])

    if needle > element:
        return bsearch(needle, haystack[half:l])




print(bsearch(7, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]))

---

在二进制搜索中:

1. 列表必须有序
2. 如@tripleee 所述，您必须递归地将列表分成两半