e二分查找——python

1.二分查找

1.定義 二分搜尋是一種在有序數組中查找某一特定元素的搜尋算法。搜尋過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜尋過程結束；如果某一特定元素大于或者小于中間元素，則在數組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜尋算法每一次比較都使搜尋範圍縮小一半。

def binarySearch(arr, l, r, x):

if r >= 1:

mid = int(1+(r-l)/2)

if arr[mid] == x:

return mid

elif arr[mid] >x:

return binarySearch(arr, 1, mid-1, x)

else:

return binarySearch(arr, 1, mid+1, x)

else:

return -1

import numpy as arr

arr = [ 2, 3, 4, 10, 40 ]

x = 10

result = binarySearch(arr, 0, len(arr)-1, x)

if result != 1:

print(“元素在數組的索引為%d”% result)

else:

print(“元素不在數組中”)

2.例題（來自www.mewcoder.com）

*請實作有重複數字的有序數組的二分查找。 輸出在數組中第一個大于等于查找值的位置，如果數組中不存在這樣的數，則輸出數組長度加一。連結：https://www.nowcoder.com/questionTerminal/7321e6f66d06433d9005aa37536f63fb

來源：牛客網

輸入描述:

第一行兩個正整數n，v(1<=n<=100000，1<=v<=100000)，分别表示數組長度與查找值。

第二行n個正整數a1,a2,…,an(1<=a1<=a2<=…<=an<=n)表示有序數組。

輸出描述:

輸出在數組中第一個大于等于查找值的位置，如果數組中不存在這樣的數，則輸出數組長度加一。*

import bisect

while True:

try:

n,k=list(map(int,input().split()))

a=list(map(int,input().split()))

index=bisect.bisect_left(a,k)+1

print(index)

except:

break