结合两个函数 1]冒泡排序 2]二分查找

Question

我有意见。 assingment 说要在 python 中编写两个函数，它们将：

使用冒泡排序对列表进行排序
从用户那里获取数字输入并在先前排序的列表中搜索该数字。

我的第一个函数 - sort - 可以排序。但是，我的第二个函数没有正确执行二进制搜索。我的最终目标是结合这两个功能。

这是我当前的代码：

冒泡排序

def sort(x):
        for j in range(len(x)):
            for i in range (len(x)-1):
                if x[i]> x[i+1]:
                    temp =x[i]
                    x[i]=x[i+1]
                    x[i+1]=temp
        return x

    sl = sort([87,56,34,23,89,15,2,200,28,31])
    print (sl)

二进制搜索

def bs(t):

    s = 0 
    e = len(t)-1
    found = False
    c = int(input("Enter"))
    while (s<=e):
        mid = (s+e)//2
        if t[mid]==c:
            found = True
        elif c > t[mid]:
            s = mid+1
        else:
            e = mid-1
    return found
bs([1,2,3,4,5])

Answer 1

问题出在您的 while 循环中。如果找到项目 s 或 e 而不是 increment/decrement 并且循环变为无限。

您应该添加 break 语句或拆分 if 条件：

def bs(t):
    t = sort(t)

    s = 0 
    e = len(t)-1
    found = False
    c = int(input("Enter"))
    while (s<=e):
        mid = (s+e)//2
        if t[mid]==c:
            found = True
            break
        elif c > t[mid]:
            s = mid+1
        else:
            e = mid-1
    return found
bs([1,2,3,4,5])

或：

def bs(t):
    t = sort(t)

    s = 0 
    e = len(t)-1
    found = False
    c = int(input("Enter"))
    while (s<=e):
        mid = (s+e)//2
        if t[mid]==c:
            found = True

        if c > t[mid]:
            s = mid+1
        else:
            e = mid-1
    return found
bs([1,2,3,4,5])

组合函数（sort + bs）:

def binary_search(x):
for j in range(len(x)):
    for i in range(len(x) - 1):
        if x[i] > x[i + 1]:
            temp = x[i]
            x[i] = x[i + 1]
            x[i + 1] = temp

    s = 0
    e = len(x)-1
    found = False
    c = int(input("Enter"))

    while s <= e:
        mid = (s + e)//2
        if x[mid] == c:
            found = True
            break
        elif c > x[mid]:
            s = mid+1
        else:
            e = mid-1

    return found

结合一些重构：

def binary_search(x):
    # j is not used, so it could be replaced with underscore
    for _ in range(len(x)):
        for i in range(len(x)-1):
            if x[i] > x[i+1]:
                # this is illustration of python awesomeness
                x[i], x[i+1] = x[i+1], x[i]

    c = int(input("Enter"))

    while x:
        # this line is actually the same as s + e, because 
        # is always equals to list's len - 1
        mid = (len(x)-1)//2

        # instead of redefining variable - just break from loop
        if x[mid] == c:
            break

        if c > x[mid]:
            # slice list instead of computing new start index
            x = x[mid+1:]
        else:
            # slice list instead of computing new last index
            x = x[:mid-1]

    return len(x) > 0  # true if x contains at least one el and false otherwise 


sl = binary_search([87, 56, 34, 23, 89, 15, 2, 200, 28, 31])
print(sl)

结合两个函数 1]冒泡排序 2]二分查找

Combining two functions 1]Bubble Sort 2]Binary Search

python

algorithm

bubble-sort

binary-search-tree

python-3.x