Python函数二分查找 python二分法查找

python中list有没有自带二分查找函数

要判断一个list中是否存在你要的东西，可以用 value in list 的方式或者 list.index(value), 具体python内部实现用的什么算法。。。自己研究吧。

创新互联专注于安源网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供安源营销型网站建设，安源网站制作、安源网页设计、安源网站官网定制、重庆小程序开发服务，打造安源网络公司原创品牌,更为您提供安源网站排名全网营销落地服务。

【python】判断一个自然数是否是某个数的平方？

题目：设计一个算法，判断给定的一个数n是否是某个数的平方，不能使用开方运算。

分析：二分查找法。查找从1~n的数字中，是否存在一个数m，使得m的平方为n。首先判断mid = (1 + n) / 2的平方power与m的大小，如果power m,那么说明在[1, mid - 1]区间继续查找，否则在[mid + 1, n]区间继续查找。

code：

def isPower(n):

low = 1

high = n

while low high:

    mid = (high + low) / 2

    power = mid * mid

    # 接着在1~mid-1区间查找

    if power n:

        high = mid - 1

    # 接着在mid+1~n区间内查找

    elif power n:

        low = mid + 1

    else:

        return True

return False

if __name__ == "__main__":

n1 = 15

if isPower(n1):

    print(str(n1) + "某个自然数的平方")

else:

    print(str(n1) + "不是某个自然数的平方")

程序的运行结果：

15不是某个自然数的平方

python 二分查找算法函数bi_search(),该函数实现检索任意一个整数在 prime() 函数生成的

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()