数据结构与算法 递归--二分查找

数据结构与算法 递归–二分查找

import os
import re
import shutil

def binary_search(data,target,low,high):
    if low>high:
        return False
    else:
        mid = (low + high)//2
        if target == data[mid]:
            return True
        elif target <data[mid]:
            return binary_search(data, target, low, mid-1)
        else:
            return binary_search(data, target, mid+1, high)
        
data = [2,4,5,7,8,9,12,14,17,19,22,25,27,28,33,57]
binary_search(data, 12, 0, 15)

典型算法递归算法–二分查找

前提：当序列有序并且可通过索引访问。
该算法维持两个参数low和high，这样可使所有的索引位于low和high之间。
首先，low=0和high=n-1。然后比较目标值和候选项中间值，即索引项[mid]的数据：

$mid = [(low + high)/2]$mid=[(low+high)/2]
需考虑以下情况：

• 如果目标刚好等于[mid]的数据，然后找到正在寻找的值，则查找成功并且终止程序。
• 如果目标值小于[mid]的数据，需对前半部分重复进行这一过程查找，即在low 和 mid -1中进行查找。
• 如果目标值大于[mid]的数据，需对后半部分重复进行这一过程查找，即在mid -1 和 high之间进行查找。
• 如果最后low大于high，说明索引范围内没有该值，则查找失败。

注：二分查找的时间复杂度为 O(㏒ n)

参考：Python结构与算法一书
算法动态展示可以使用网站：https://visualgo.net/zh