国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 編程 > Python > 正文

python二分法實現實例

2020-02-23 04:59:01
字體:
來源:轉載
供稿:網友

1.算法:(設查找的數組期間為array[low, high])

(1)確定該期間的中間位置K
(2)將查找的值T與array[k]比較。若相等,查找成功返回此位置;否則確定新的查找區域,繼續二分查找。區域確定如下:
a.array[k]>T 由數組的有序性可知array[k,k+1,……,high]>T;故新的區間為array[low,……,K-1]
b.array[k]<T 類似上面查找區間為array[k+1,……,high]。每一次查找與中間值比較,可以確定是否查找成功,不成功當前查找區間縮小一半。遞歸找,即可。

2.python代碼:

代碼如下:
#!/usr/bin/python
# -*- coding: utf-8 -*-

def BinarySearch(array,t):
    low = 0
    height = len(array)-1
    while low < height:
        mid = (low+height)/2
        if array[mid] < t:
            low = mid + 1

        elif array[mid] > t:
            height = mid - 1

        else:
            return array[mid]

    return -1


if __name__ == "__main__":
    print BinarySearch([1,2,3,34,56,57,78,87],57)

結果:57

3.時間復雜度:O(log2n);

注意:二分查找的前提必須待查找的序列有序。

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 雅江县| 松潘县| 亳州市| 荔浦县| 仁寿县| 抚松县| 房产| 邳州市| 崇明县| 彭阳县| 阿尔山市| 南安市| 中阳县| 八宿县| 洪湖市| 丰台区| 江安县| 正蓝旗| 抚松县| 固始县| 黔西| 敦化市| 栾川县| 汉阴县| 常宁市| 富锦市| 蓝田县| 松阳县| 龙海市| 大埔县| 陈巴尔虎旗| 姜堰市| 缙云县| 秀山| 临邑县| 黄浦区| 定结县| 绥江县| 新龙县| 江安县| 沾益县|