摘要：在排好序的單詞列表中查找某個(gè)單詞優(yōu)化和的初始化，從開(kāi)始，這樣避免只有時(shí)的優(yōu)化減少了內(nèi)存溢出的風(fēng)險(xiǎn)優(yōu)化循環(huán)時(shí)，。

迭代法（Iterative Method），簡(jiǎn)單來(lái)說(shuō)，其實(shí)就是不斷地用舊的變量值，遞推計(jì)算新的變量值。循環(huán)。

求數(shù)值的精確/近似解

二分法（Bisection method）

牛頓迭代法（Newton’s method）

在一定范圍內(nèi)查找目標(biāo)值

二分查找

機(jī)器學(xué)習(xí)中的迭代算法

K-均值算法（K-means clustering）

PageRank 的馬爾科夫鏈（Markov chain）

梯度下降法（Gradient descent）

求方程的精確/近似解

二分法

#"""計(jì)算某個(gè)給定正整數(shù) n（n>1）的平方根，如果不使用編程語(yǔ)言"""
# delta_threshold:允許的誤差的閾值
# max_try：最大嘗試次數(shù)
def get_squre_root(n,delta_threshold=0.000000000000001,max_try=1000):
    if n <= 1:
        return -1
    min = 1.0
    n = float(n)
    max = n
    mid = (max+min)/2.0
    print(mid)
    for i in range(max_try):
        _n = mid * mid
        delta = _n-n
        if delta == 0:
            print("精確值")
            return mid
        
        abs_delta = abs(delta)
        if abs_delta <= delta_threshold:
            print("近似值")
            return mid
        else:
            if delta>0:
                max = mid
            else:
                min = mid
            mid = (max+min)/2.0
            print(mid)
    return min

get_squre_root(16)

牛頓迭代法
之后補(bǔ)充

查找匹配記錄
快速查找記錄，除了用字典，還可以用著名的 二分查找法（前提是有序）。這也是迭代逼近的典型案例。

二分查找，第一版

#在排好序的單詞列表中查找某個(gè)單詞
#@ param words_list,target_word
#@ return bool
def search(words_list,target_word):
    if not words_list:
        return False
    
    min = 1
    max = len(words_list)
    while True:
        mid = (max + min)/2
        mid_word = words_list[mid]
        if target_word == mid_word:
            print(mid)
            return True
        elif target_word > mid_word:
            min = mid
        else:
            max = mid

        if max <= min:
            return False

    return False
# words_list = ["i","love","my","wife","than","myself"s","body","."]
words_list = ["e"]
words_list = sorted(words_list)
print(words_list)
print(search(words_list,"i"))

二分查找，改完bug后，第二版

#在排好序的單詞列表中查找某個(gè)單詞
#@ param words_list,target_word
#@ return bool
# 優(yōu)化1: min和max的初始化，從0開(kāi)始，這樣避免只有l(wèi)en(list)=1時(shí)的bug
# 優(yōu)化2: mid = min + (max - min)/2 ,減少了內(nèi)存溢出的風(fēng)險(xiǎn)
def search(words_list,target_word):
    if not words_list:
        return False
    
    min = 0
    max = len(words_list) - 1
    while True:
        mid = min + (max - min)/2
        mid_word = words_list[mid]
        if target_word == mid_word:
            print(mid)
            return True
        elif target_word > mid_word:
            min = mid
        else:
            max = mid

        if max <= min:
            return False

    return False
words_list = ["i","love","my","wife","than","myself"s","body","."]
# words_list = ["e"]
words_list = sorted(words_list)
print(words_list)
print(search(words_list,"i"))

二分查找，再改bug后，第三版（應(yīng)該沒(méi)bug了吧。。）

#在排好序的單詞列表中查找某個(gè)單詞
#@ param words_list,target_word
#@ return bool
# 優(yōu)化1: min和max的初始化，從0開(kāi)始，這樣避免只有l(wèi)en(list)=1時(shí)的bug
# 優(yōu)化2: mid = min + (max - min)/2 ,減少了內(nèi)存溢出的風(fēng)險(xiǎn)
# 優(yōu)化3: 循環(huán)時(shí)，min = mid + 1。和max = mid - 1。減少重復(fù)檢查邊界
# 優(yōu)化4: 跳出循環(huán)的條件改為max < min，避免最后一步出現(xiàn)max=min=target的潛在bug
def search(words_list,target_word):
    if not words_list:
        return False
    
    min = 0
    max = len(words_list) - 1
    while True:
        mid = min + (max - min)/2
        mid_word = words_list[mid]
        if target_word == mid_word:
            print(mid)
            return True
        elif target_word > mid_word:
            min = mid + 1
        else:
            max = mid - 1

        if max < min:
            print(max)
            return False

    return False
words_list = ["i","love","my","wife","than","myself"s","body","."]
# words_list = ["e"]
words_list = sorted(words_list)
print(words_list)
print(search(words_list,"i"))

迭代法的特點(diǎn)是“分而治之”，不斷重復(fù)一個(gè)相似的行為，一步步地縮小目標(biāo)范圍。計(jì)算機(jī)很適合處理這種重復(fù)的工作，而人類并不擅長(zhǎng)，所以有時(shí)候不敏感。在編程的時(shí)候，可以特意留意這一差異。