二分查找算法原理和实现

我会带着你远行 2023-06-13 15:28 12阅读 0赞

二分查找是一种比较高效的搜索算法，是一种可以在有序数组中搜索到特定元素的算法。

例如，我们要在数组\{1,4,6,10,20\}中搜索4

1.  首先与数组的中间位置的数值即6进行比较，4比6小，所以，要往左边继续搜索，左边的数组即为\{1,4\}；
2.  还是先找到数组的中间位置，这次因为是偶数，我们就取1吧（这里是按照自己取中间位置的算法实际去取），4比1小，那么要往右边数组搜索，右边数组即为\{4\}；
3.  那么，数组只有一个元素，那么中间位置肯定就是自己了即4，发现就是我们搜索，那么可以返回
    
    二分查找一般有两种实现方法：使用递归和不使用递归。

# 非递归实现 #

def search(arr, target):
        """ 不使用递归的二分查找 :param arr: 待查询数组 :param target: 查找目标 :return: """
        left = 0
        right = len(arr) - 1
    
        while left <= right:
            mid = int((left + right) / 2)
            if arr[mid] == target:
                return mid
            elif arr[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        return -1

# 递归实现 #

def search2(arr, target):
        index = search_recursion(arr, target, 0, len(arr)-1)
        return index
    
    
    def search_recursion(arr, target, left, right):
        if left > right:
            return -1
        mid = int((left + right) / 2)
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            return search_recursion(arr, target, left, mid-1)
        else:
            return search_recursion(arr, target, mid+1, right)

欢迎关注同名公众号：“我就算饿死也不做程序员”。  
交个朋友，一起交流，一起学习，一起进步。![在这里插入图片描述][20200430114531724.jpg]

[20200430114531724.jpg]: https://img-blog.csdnimg.cn/20200430114531724.jpg