深夜來臨我還不想入睡，無聊的我想起已經好幾天沒有更新文章，不知道寫點什么，我突然想到我對于演算法這方面的知識還是太淺
所以我決定在開一個專欄，就叫做 資料結構和演算法的混合雙打
二分查找
二分法是一個查找演算法，就是在一堆資料集里面找到你想要的那個資料
條件：
資料必須是有序序列
例如： [12,15,86,95,105,334,911,1000] 可以不是連續的，但是必須要是從小到大排列的，不能違背這個原則，這同樣也是它的一個小小小小小 缺點
核心思想：
掐頭結尾取中間
優點：
我稱它為查找界的鼻祖，查找速度快，效率極高
好的概念就說這么多，接下來代碼 showtime！！
一、最最最low 的寫法
# 我們先來搞一個陣列吧
list01 = [20, 45, 56, 79, 90, 110, 221, 285, 356, 618, 985, 1004]
# 接收要查找的數字
num = int(input("請輸入你要查找的數字："))
## 假如我們不用演算法的情況下，是不是就像下面這樣寫
for item in list01:
if num == item：
print("啊我找到了")
break
這樣就是我把串列的每一項拿出來，一個一個對比，如果相等就找到了，沒找到就一直找，什么時候找到算什么時候
這種查找為什么low呢，因為，你資料量少的時候，你可以這樣寫，那假如要是從幾億幾十億資料里面找，那么你這樣就要找幾億幾十億次，就顯得效率特別低
二、高級的演算法：二分法查找
# 二分法查找核心思想：掐頭結尾取中間
# 位置 left mid right
# 索引 0 1 2 3 4 5 6 7 8 9 10 11
# list01 = [20, 45, 56, 79, 90, 110, 221, 285, 356, 618, 985, 1004]
# 找到 頭 和 尾
left = 0 # 取得串列的頭部，這個最開始是 20 ，那么它的索引就是 0
right = len(list01) -1 # 尾部是1004， 那么索引就是 11
# 取中間
mid = (left + right) // 2 # 左邊加右邊等于索引0+11，然后整除于2
注意： 必須整除，因為你要是 / 2 的話，就容易出現小數點 .5 這樣的，在我們 索引中是沒有點幾 這個概念的
接下來我們為了演示輸入一個存在的數字90，然后和中間的mid這個數做比較，那么我們在現在中間的是110
90比110小，且串列是從小到大排列的，所以這個數字絕對不可能出現在串列的右邊
一定會出現在串列的左邊，那么我們就應該去移動右邊界到mid的前一位
也就是：
# 位置 left right mid
# 索引 0 1 2 3 4 5 6 7 8 9 10 11
# list01 = [20, 45, 56, 79, 90, 110, 221, 285, 356, 618, 985, 1004]
那么反之就是比中間數字大，就是right不變，left向右移動唄
根據上面的分析所以接下來我們就寫演算法程序了：
if num > list01[mid]:
left = mid + 1
elif num < list01[mid]:
right = mid - 1
else:
print("我找到啦，這個數字在%s位置" % mid)
這樣我們的大致的演算法主體邏輯就寫完了，但是這樣寫只是寫了一步，我只是計算了第一次
也就是第一次移動，我們不能保證它移動一次就找到了
所以接下來我們應該是類似于這樣寫，加一個回圈，然后讓它一直找，找到直接break
while 1:
# 要一直定義中間值
mid = (left + right) // 2
if num > list01[mid]:
left = mid + 1
elif num < list01[mid]:
right = mid - 1
else:
print("我找到啦，這個數字在%s位置" % mid)
break
那么我們千算萬算還是欠點考慮，就是那你輸入的這個數字不存在怎么辦，我輸入了一個60
它就會一直找找找，不斷回圈，因為left是要一直加1，而right是要一直減1
總有一次 left會到right左邊，right會到left右邊，這樣就代表左右都找過了，我們在找下去就沒有意義了
# 位置 right left
# 索引 0 1 2 3 4 5 6 7 8 9 10 11
# list01 = [20, 45, 56, 79, 90, 110, 221, 285, 356, 618, 985, 1004]
所以我們代碼最終應該是這樣的：
list01 = [20, 45, 56, 79, 90, 110, 221, 285, 356, 618, 985, 1004]
num = int(input("請輸入你要查找的數字："))
left = 0
right = len(list01) - 1
while left <= right: # 當左邊比右邊小的時候才有意義，反之不存在
# 要一直定義中間值
mid = (left + right) // 2
if num > list01[mid]:
left = mid + 1
elif num < list01[mid]:
right = mid - 1
else:
print("我找到啦，這個數字在%s位置" % mid)
break
else:
print("抱歉，你找數字不存在")
我上面說它的效率是非常高的，我們舉個例子：
# 一億資料，用二分查找
1、100000000
2、50000000
3、25000000
4、.....
最終我們可以計算出查找一億資料最多只要二分查找27次，就可以全部找一遍
也就是2的幾次方，我們去轉換成log以2為底的對數進行計算
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/286802.html
標籤：其他