七大查找

分类方法

一、二分查找
二、

一、二分查找

1.思路

要求必须是有序列表

2.两种写法

1.递归查找
2.非递归查找

1.递归查找

# -*- coding: UTF-8 -*-


def binary_search1(arr, left, right, num):

    if left > right: #递归结束条件
        return -1
    mid = (left + right) // 2
    if num < arr[mid]:
        right = mid -1
    elif num > arr[mid]:
        left = mid + 1
    else:
        return mid
    return binary_search(arr, left, right, num)
    #这里之所以会有return是因为必须要接收值，不然返回None
    #回溯到最后一层的时候，如果没有return，那么将会返回None

arr = [11, 32, 51, 21, 42, 9, 5, 6, 7, 8]
print(arr)
arr.sort()
print(arr)
res = binary_search1(arr, 0, len(arr)-1,9)
print(res)

2.非递归查找

# -*- coding: UTF-8 -*-


def binary_search(arr, num):
    left = 0
    right = len(lis) - 1
    while left <= right:   #循环条件
        mid = (left + right) // 2   #获取中间位置，数字的索引（序列前提是有序的）
        if num < arr[mid]:  #如果查询数字比中间数字小，那就去二分后的左边找，
            right = mid - 1   #来到左边后，需要将右变的边界换为mid-1
        elif num > arr[mid]:   #如果查询数字比中间数字大，那么去二分后的右边找
            left = mid + 1    #来到右边后，需要将左边的边界换为mid+1
        else:
            return mid  #如果查询数字刚好为中间值，返回该值得索引
    return -1  #如果循环结束，左边大于了右边，代表没有找到

arr = [11, 32, 51, 21, 42, 9, 5, 6, 7, 8]
print(arr)
lis.sort()
print(arr)
res = binary_search(arr, 9)
print res