二进制搜索 python 3.5

Question

我正在尝试在 python 3.5 中编写二进制搜索，但它不起作用我不确定为什么。

def binarySearch(alist, value):

    first = 0
    last = len(alist)-1
    midpoint = (last//2)
    while binarySearch:
        if value == alist[midpoint]:
            return True and print ("found")
        else:
            if value < midpoint:
                last = midpoint-1
            else:
                if value > midpoint:
                    first = midpoint+1    
binarySearch([1,2,3,4,5,6,7,8],3)

如果我将值设置为 4，它会显示已找到，如果我输入任何其他值，则不会发生任何事情，并且它会卡住运行什么都不做。

感谢您的帮助。

Answer 1

你的循环条件是错误的while binarySearch?
您只需更改一次中点的值，而应该在每次循环迭代时更改它。
您将值与指数（中点）进行比较并且应该与列表值 (alist[midpoint])
这是错误的：return True and print ("found")它总是returnNone。

Answer 2

User1915011 先于我回答。根据他的回答和@wim 的评论，我对您的 binarySearch 方法进行了以下更改。

将循环更改为使用 found 变量
在循环内 midpoint 添加了额外的赋值
通过添加 first<=last

Return在while循环后找到，表示成功或失败。

def binarySearch(alist, value):

    first = 0
    last = len(alist)-1
    found = False
    while first<=last and not found:
        midpoint = (first + last)//2
        if value == alist[midpoint]:        
            found =  True 
        else:
            if value < alist[midpoint]:
                last = midpoint-1
            else:
                if value > midpoint:
                    first = midpoint+1  
    return found

if binarySearch([1,2,3,4,5,6,7,8],3):
    print "found"

Answer 3

二进制转换器也很酷

num = int(input('please enter your number: '))  
list = []  
for i in (128, 64, 32, 16, 8, 4, 2, 1):  
    if num >= i:  
        list.append(1)  
        num = num-i  
    else:  
        list.append(0)
print(list)

Answer 4

这里详细解释了它是如何工作的：

    def binarySearch(array, i):

    ## Binary search is the algorithm which is used to search an element in a sorted array

    ## The time complexity of the binary search is O(log n)
    ## Which means that in an array of length(2^(n-1)) elements we need to look at only n elements
    ## That is why we say that binary search algorithm runs in logarithmic time, which is much faster than linear time

    start = 0
    last = len(array)-1
    result = False

    count = 0 ## to debug

    print("\n******************************************************************\n")
    while(start <= last and not result):

        ## Debugger Begin
        mid = 0
        print("Loop number: ", count)
        print("Start element: ", array[start], " Position of Start Element: ", start)
        print("Last element: ", array[last], "  Position of Last Element: ", last)
        ## Debugger End

        mid = (start + last)//2 ## '//' indicates the floor division(ignores the value after the period) 
        if(array[mid] == i):
            print("***Mid***")
            result = True;
        else:
            if(i < array[mid]):
                print("***The value of the item:",i," we are searching for is LESS than the current middle element***")
                last = mid - 1
            else:
                print("***The value of the item:",i," we are searching for is GREATER than the current middle element***")
                start = mid + 1

        ## Debugger
        count = count+1
        print("Mid element: ", array[mid], "   Position of Mid Element: ", mid, "\n")
        ## Debugger

    print("******************************************************************")
    if(result == True):
        print("\nThe element:",i ,"is in the array")
    else:
        print("\nItem is not in the array")

    return result

## Array you want to search
array = [9, 11, 12, 21, 23, 34, 45, 49, 65, 98]

## Item you want to search in the array
i = 21

print("Searching the element: ",i , "\nIn the Array: ", array)
print("Length of the array is: ", len(array))

## Binary Search
binarySearch(array, i)

二进制搜索 python 3.5

Binary Search python 3.5

python

runtime-error

binary-search

python-3.5