二分法查找python

⑴ 關於python里的二分法

因為他已經把middle位置上的數字已經檢查過了，第一個if條件就是判斷middle位置山的數字是不是想要的，既然這個條件不滿足，那麼就肯定不需要他，所以從他的上一位或下一位重新開始

⑵ python實現折半查找和歸並排序演算法

python實現折半查找和歸並排序演算法
今天依舊是學演算法，前幾天在搞bbs項目，界面也很醜，評論功能好像也有BUG。現在不搞了，得學下演算法和數據結構，筆試過不了，連面試的機會都沒有……
今天學了折半查找演算法，折半查找是蠻簡單的，但是歸並排序我就挺懵比，看教材C語言寫的歸並排序看不懂，後來參考了別人的博客，終於搞懂了。
折半查找
先看下課本對於 折半查找的講解。注意了，折半查找是對於有序序列而言的。每次折半，則查找區間大約縮小一半。low,high分別為查找區間的第一個下標與最後一個下標。出現low>high時，說明目標關鍵字在整個有序序列中不存在，查找失敗。

看我用python編程實現:
defBinSearch(array, key, low, high): mid=int((low+high)/2) ifkey==array[mid]:# 若找到 returnarray[mid] iflow > high: returnFalse ifkey < array[mid]: returnBinSearch(array, key, low, mid-1)#遞歸 ifkey > array[mid]: returnBinSearch(array, key, mid+1, high) if__name__=="__main__": array=[4,13,27,38,49,49,55,65,76,97] ret=BinSearch(array,76,0,len(array)-1)# 通過折半查找，找到65 print(ret)
輸出: 在列表中查找76.
76
時間復雜度：O(logn)
歸並排序演算法
先闡述一下排序思路：
首先歸並排序使用了二分法，歸根到底的思想還是分而治之。歸並排序是指把無序的待排序序列分解成若干個有序子序列，並把有序子序列合並為整體有序序列的過程。長度為1的序列是有序的。因此當分解得到的子序列長度大於1時，應繼續分解，直到長度為1.
(下圖是分解過程，圖自python編程實現歸並排序)

合並的過程如下:

很好，你現在可以和別人說，老子會歸並排序了。但是讓你寫代碼出來，相信你是不會的……
來來來，看我用python寫的歸並排序演算法:
defmerge_sort(array):# 遞歸分解 mid=int((len(array)+1)/2) iflen(array)==1:# 遞歸結束的條件，分解到列表只有一個數據時結束 returnarray list_left=merge_sort(array[:mid]) list_right=merge_sort(array[mid:]) print(">>>list_left:", list_left) print(">>>list_right:", list_right) returnmerge(list_left, list_right)# 進行歸並 defmerge(list_left, list_right):# 進行歸並 final=[] whilelist_leftandlist_right: iflist_left[0] <=list_right[0]:# 如果將"<="改為"<",則歸並排序不穩定 final.append(list_left.pop(0)) else: final.append(list_right.pop(0)) returnfinal+list_left+list_right# 返回排序好的列表 if__name__=="__main__": array=[49,38,65,97,76] print(merge_sort(array))輸出:
輸出：
>>>list_left: [49]
>>>list_right: [38]
>>>list_left: [38, 49]
>>>list_right: [65]
>>>list_left: [97]
>>>list_right: [76]
>>>list_left: [38, 49, 65]
>>>list_right: [76, 97]
[38, 49, 65, 76, 97]
時間度雜度: 平均情況＝最好情況＝最壞情況＝O(nlogn)
空間復雜度:O(n)
穩定性:穩定
對序列{ 6, 5, 3, 1, 8, 7, 2, 4 }進行歸並排序的實例如下:

使用歸並排序為一列數字進行排序的宏觀過程:

以上就是本文的全部內容，希望對大家的學習有所幫助

⑶ 誰會用python寫個二分法查找的循環

#!/usr/bin/envpython
importsys

defsearch2(a,m):
low=0
high=len(a)-1
while(low<=high):
mid=(low+high)/2
midval=a[mid]

ifmidval<m:
low=mid+1
elifmidval>m:
high=mid-1
else:
printmid
returnmid
print-1
return-1

if__name__=="__main__":
a=[int(i)foriinlist(sys.argv[1])]
m=int(sys.argv[2])
search2(a,m)

⑷ 一個二分法搜索的python小程序，為什麼按回車以後沒有用

沒寫個py腳本里？你把函數調用也寫在函數里了，所以，你的函數沒有調用。注意縮進

⑸ 二分法的演算法步驟是什麼

在有序的有N個元素的數組中查找用戶輸進去的數據x。

演算法如下：

1、確定查找范圍front=0，end=N-1，計算中項mid=（front+end）/2。

2、若a[mid]=x或front>=end，則結束查找；否則，向下繼續。

3.、若a[mid]<x，說明待查找的元素值只可能在比中項元素大的范圍內，則把mid+1的值賦給front，並重新計算mid，轉去執行步驟2；若a[mid]>x，說明待查找的元素值只可能在比中項元素小的范圍內，則把mid-1的值賦給end，並重新計算mid，轉去執行步驟2。

(5)二分法查找python擴展閱讀

基本思想：假設數據是按升序排序的，對於給定值key，從序列的中間位置k開始比較，

如果當前位置arr[k]值等於key，則查找成功；

若key小於當前位置值arr[k]，則在數列的前半段中查找，arr[low，mid-1]；

若key大於當前位置值arr[k]，則在數列的後半段中繼續查找arr[mid+1，high]，

直到找到為止，時間復雜度:O(log(n))。

⑹ 如何用二分法檢索搜索開頭字母 python

#!/usr/bin/envpython
#encoding:utf-8
defhalf_search(search_arr,search_str):
lb=0
ub=len(search_arr)-1
foriinrange(ub/2+1):
iflb>ub:
return-1
mid=(ub+lb)/2
ifsearch_arr[mid]==search_str:
returnmid
elifsearch_arr[mid]>search_str:
ub=mid-1
else:
lb=mid+1
if__name__=='__main__':
arr=[10,20,30,40,50,60,70]
printhalf_search(arr,1)
printhalf_search(arr,11)
printhalf_search(arr,22)
printhalf_search(arr,33)
printhalf_search(arr,40)
printhalf_search(arr,55)
printhalf_search(arr,66)
printhalf_search(arr,70)
printhalf_search(arr,8)

結果：

-1
-1
-1
-1
3
-1
-1
6
-1

⑺ python基礎在線求解

(1) 10;5;10
(2)查找成功平均次數是10（有一半成功幾率應該是5次，但演算法估算是去常數的，所以用O表示還是10），不成功就是10
（3）二分是4次，不成功也是4次

a=[34,56,78,87,88,90,101,112,520,888]

defbinsearch(num):
start=0
end=len(a)-1
whilestart<=end:
mid=(start+end)//2
ifnum==a[mid]:
returnmid
elifnum>a[mid]:
start=mid+1
else:
end=mid-1
return-1

print(binsearch(8))

⑻ Python中的枚舉法,隨機法和二分法的優點是什麼

摘要 枚舉法的優缺點主要是：優點由於枚舉法一般是現實生活中問題的「直譯」，因此比較直觀，易於理解；枚舉法建立在考察大量狀態、甚至是窮舉所有狀態的基礎上，所以演算法的正確性比較容易證明。