基础算法 ---> 二分法

时间:2022-02-04 04:04:50

二分法本质:

  二分法是以数组中间为分界线(这里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))

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