python中l(wèi)ist有沒有自帶二分查找函數(shù)

要判斷一個list中是否存在你要的東西，可以用 value in list 的方式或者 list.index(value), 具體python內部實現(xiàn)用的什么算法。。。自己研究吧。

創(chuàng)新互聯(lián)專注于安源網(wǎng)站建設服務及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗。 熱誠為您提供安源營銷型網(wǎng)站建設，安源網(wǎng)站制作、安源網(wǎng)頁設計、安源網(wǎng)站官網(wǎng)定制、重慶小程序開發(fā)服務，打造安源網(wǎng)絡公司原創(chuàng)品牌,更為您提供安源網(wǎng)站排名全網(wǎng)營銷落地服務。

【python】判斷一個自然數(shù)是否是某個數(shù)的平方？

題目：設計一個算法，判斷給定的一個數(shù)n是否是某個數(shù)的平方，不能使用開方運算。

分析：二分查找法。查找從1~n的數(shù)字中，是否存在一個數(shù)m，使得m的平方為n。首先判斷mid = (1 + n) / 2的平方power與m的大小，如果power m,那么說明在[1, mid - 1]區(qū)間繼續(xù)查找，否則在[mid + 1, n]區(qū)間繼續(xù)查找。

code：

def isPower(n):

low = 1

high = n

while low high:

? ? mid = (high + low) / 2

? ? power = mid * mid

? ? # 接著在1~mid-1區(qū)間查找

? ? if power n:

? ? ? ? high = mid - 1

? ? # 接著在mid+1~n區(qū)間內查找

? ? elif power n:

? ? ? ? low = mid + 1

? ? else:

? ? ? ? return True

return False

if __name__ == "__main__":

n1 = 15

if isPower(n1):

? ? print(str(n1) + "某個自然數(shù)的平方")

else:

? ? print(str(n1) + "不是某個自然數(shù)的平方")

程序的運行結果：

15不是某個自然數(shù)的平方

python 二分查找算法函數(shù)bi_search(),該函數(shù)實現(xiàn)檢索任意一個整數(shù)在 prime() 函數(shù)生成的

def?prime(n):

if?n=2:

return?[]

result=[False,False]+[True]*(n-2)

for?i?in?range(len(result)):

if?result[i]==True:

for?j?in?range(2*i,len(result),i):

result[j]=False

return?[i?for?i?in?range(len(result))?if?result[i]==True]

def?bi_search(prime,primelist,start,end):

if?startend?:

return?-1

mid=(start+end)//2

if?primelist[mid]==prime:

return?mid

elif?primelist[mid]prime:????????????????

end=mid-1

else:

start=mid+1

return?bi_search(prime,primelist,start,end)

if?__name__=='__main__':

n=int(raw_input())

primelist=prime(n)

num=raw_input()

while?num:

num=int(num)

index=bi_search(num,primelist,0,len(primelist)-1)

print(index)

num=raw_input()