数据结构-查找-二分查找法

╰+哭是因爲堅強的太久メ 2023-10-04 16:28 69阅读 0赞

#### 二分查找法 ####

如果要查找的数据已经实现拍好了顺序，就可以使用二分查找法来进行查找。二分查找法是将数据分割成两等分，再比较键值与中间值的大小，如果键值小于中间值，就可以确定要查找的数据在前半段，否则在后半段。如此分割直到找到或者确定不存在为止。例如，已排序的数列为2，3，5，8，9，11，12，16，18，而所需查找的是11时：

首先跟第5个值9比较

因为11>9，所以和后半部分中间值12比较

因为11<12，所以和后半部分的前半部分的中间值11比较

因为11=11，表示查找完成，如果不相等，就表示找不到

**设计一个程序，随机生成1-150的50个数字，使用二分法查找**

#使用快排对数组进行排序
    import random
    
    
    def quickSort(d,size,lf,rg):
        if lf < rg:     #排序数列的左边和右边
            lf_idx = lf + 1
            while d[lf_idx] < d[lf]:
                if lf_idx >= size:
                    break
                lf_idx += 1
            rg_idx = rg
            while d[rg_idx] > d[lf]:
                rg_idx -= 1
            while lf_idx < rg_idx:
                d[lf_idx],d[rg_idx] = d[rg_idx],d[lf_idx]
                lf_idx += 1
                while d[lf_idx] < d[lf]:
                    lf_idx += 1
                rg_idx -= 1
                while d[rg_idx] > d[lf]:
                    rg_idx -= 1
            d[lf],d[rg_idx] = d[rg_idx],d[lf]
            #分割前后接着递归排序
            quickSort(d,size,lf,rg_idx - 1)
            quickSort(d,size,rg_idx + 1,rg)
    
    #二分查找法
    def binSearch(data,val):
        low = 0
        high = len(data)
        while low < high and val != -1:
            mid = int((low + high) / 2)
            if val < data[mid]:
                high = mid - 1
            elif val > data[mid]:
                low = mid + 1
            else:
                return mid
        return -1
    
    def main():
        val = 1
        data = [0] * 50
        for i in range(50):
            data[i] = random.randint(1,150)
        #为数组排序
        quickSort(data,len(data),0,len(data)-1)
        #数组内容
        for i in range(5):
            for j in range(10):
                print('%2d [%3d] '%(i*10+j+1,data[i*10+j]),end='')
            print()
        #二分法查找
        while True:
            num = 0
            val = int(input("请输入查找值(1-150),输入-1结束："))
            if val == -1:
                break
            num = binSearch(data,val)
            if num == -1:
                print("=============没有找到[%2d]============="%val)
            else:
                print('在第%2d的位置找到了%3d'%(num+1,data[num]))
    
    if __name__ == '__main__':
        main()

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210702131801746.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA==,size_16,color_FFFFFF,t_70