基础算法 ---> 二分法

二分法本质：

　　二分法是以数组中间为分界线(这里k为中间索引)，

　　当array[k] > num 则继续搜索数组前半部分

　　当array[k] < num 则继续搜索数组后半部分

　方法一：　

def BinarySearch(array,num):
    low = 0
    height = len(array)-1
    while low <= height:
        mid = (low+height)//2
        if array[mid] < num:    
            low = mid + 1

        elif array[mid] > num:
            height = mid - 1

        else:
            return array[mid]

    return -1

print (BinarySearch([1,2,3,34,56,57,78,87],87))

方法二：

def bs(array, num):
    while len(array):
        k = len(array) // 2
        if array[k] < num:
            array = array[k+1::]
        elif array[k] > num:
            array = array[0:k]
        else:
            return array[k]
    return

array = [1, 2 ,3, 4, 5, 6, 8, 9]
print(bs(array, 5))

注意：二分法只能查找有序的数列　　　　　　

优质内容筛选与推荐>>
1、jQuery获取Select选择的Text和Value
2、1130 冲刺2
3、HDOJ 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活
4、文件路径带有字符串的处理方法
5、自定义过滤器和标签

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看