请问哪里的问题第一次写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？或者你的假设根本不出现重复值？