算法之二分查找

柔光的暖阳◎ 2022-04-17 03:58 300阅读 0赞

# 概念 #

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到想要查找的元素，或是区间被缩小为0。

# 时间复杂度 #

二分查找的时间复杂度为 O ( l o g n ) O(logn) O(logn)

l o g n logn logn是一个非常恐怖的数量级，即使n非常大，对应的 l o g n logn logn也很小。比如n等于2的32次方，这个数很大，大约42亿。也就是说，我们在42亿个数据中用二分查找进行查找，查找到一个元素只需要比较32次。

# 二分查找的递归实现 #

Python：

def main():
            s_raw = input()
            s_string = s_raw.split(",")
            s_num = [int(x) for x in s_string]
            v = int(input())
            print bsearch(s_num, 0, len(s_num), v)
    
    def bsearch(s, low, high, v):
            mid = (low + high)/2
            if s[mid] == v:
                    return mid
            elif v < s[mid]:
                    high = mid
                    return bsearch(s, low , high, v)
            else:
                    low = mid
                    return bsearch(s, low, high, v)
    
    main()

# 二分查找应用场景 #

1.  静态：数据插入和删除操作不频繁
2.  连续：数据必须是排序好的
3.  数组存储：必须使用数组存储而非链表存储
4.  大小刚好合适：太大的情况下可能在内存中难以找到一块连续的地址空间，太小的话还不如使用遍历方便。

# 二分查找的几个变形问题 #

1.查找第一个值等于给定值的元素

def main():
            s_raw = input()
            s_list = s_raw.split(",")
            s = [int(x) for x in s_list]
    
            v = int(input())
            low = 0
            high = len(s) - 1
            print(bsearch(s, low, high, v))
    
    def bsearch(s, low, high, v):
            while(low <= high):
                    mid = (low + high) / 2
                    if s[mid] > v:
                            high = mid - 1
                    elif s[mid] < v:
                            low = mid + 1
                    else:
                            if mid == 0 or s[mid - 1] != v:
                                    return mid
                            else:
                                    high = mid - 1
            return -1
    
    main()

2.查找最后一个值等于给定值的元素

def main():
            s_raw = input()
            s_list = s_raw.split(",")
            s = [int(x) for x in s_list]
    
            v = int(input())
            low = 0
            high = len(s) - 1
            print(bsearch(s, low, high, v))
    
    def bsearch(s, low, high, v):
            while(low <= high):
                    mid = (low + high) / 2
                    if s[mid] > v:
                            high = mid - 1
                    elif s[mid] < v:
                            low = mid + 1
                    else:
                            if mid == len(s)-1 or s[mid + 1] != v:
                                    return mid
                            else:
                                    low = mid + 1
            return -1
    
    main()

3.查找第一个大于等于给定值的元素

def main():
            s_raw = input()
            s_list = s_raw.split(",")
            s = [int(x) for x in s_list]
    
            v = int(input())
            low = 0
            high = len(s) - 1
            print(bsearch(s, low, high, v))
    
    def bsearch(s, low, high, v):
            while(low <= high):
                    mid = (low + high) / 2
                    if s[mid] < v:
                            low = mid + 1
                    else:
                            if mid == 0 or s[mid - 1] < v:
                                    return mid
                            else:
                                    high = mid - 1
            return -1
    
    main()

4.求循环有序数组如4、5、6、1、2、3中的某个数（二分查找）

def main():
            s_raw = input()
            s_list = s_raw.split(",")
            s = [int(x) for x in s_list]
    
            v = int(input())
            low = 0
            high = len(s) - 1
            print(bsearch(s, low, high, v))
    
    
    def bsearch(s, low, high, v):
            while(low <= high):
                    mid = (low + high) / 2
                    if s[mid] > v:
                            if s[low] > v:
                                    low = mid + 1
                            else:
                                    high = mid - 1
                    elif s[mid] < v:
                            low = mid + 1
                    else:
                            return mid
    main()