请问哪里的问题第一次写python (Binary Search)

Question

#!/usr/bin/python

""" 折半查找算法
"""

#定义函数

def BinarySearch(a, X, N):
    left, right = 0, N-1
    while (left <= right):
        middle = ( left + right ) / 2
        if (X < a[middle]):
            right = middle - 1
        elif (X > a[middle]):
            left = middle + 1
        else:
            return middle
    return -1 #"not found"

#调用函数

arr = [10,20,30,40,50,60,70]
BinarySearch(arr, 40, len(arr))

Answer 1

是这里middle = ( left + right ) / 2，求出来的是浮点数，应该转成int就可以了int(middle)

Answer 2

#!/usr/bin/python # -*- coding: utf-8 -*- import random # generate an unsorted list def generate_unsorted_list(num): unsorted_list = [] for i in range(0, num): unsorted_list.append(random.randint(0, 30)) print unsorted_list return unsorted_list def binary_search(target, sorted_list): list_length = len(sorted_list) start, end = 0, list_length-1 if list_length == 0: print 'empty list' return -1 while start < end: middle = (start+end)/2 if target == sorted_list[middle]: print 'find index:', middle return middle elif target < sorted_list[middle]: end = middle-1 else: start = middle+1 print 'not find' return -1 if __name__ == "__main__": unsorted_list = generate_unsorted_list(20) sorted_list = sorted(unsorted_list) print sorted_list binary_search(14, sorted_list)

Answer 3

二分查找的写法要看你的需求，对于arr = [40,40,40]你是希望返回0还是1还是2？或者你的假设根本不出现重复值？