非常感謝可以發問! 請問一下各位大大, 為何執行程式的時候輸入68,
我會一直進入while 迴圈 print 出
"68 介於中間值位置 24[ 67] 及 50[148] ,找右半邊" 的提示?
# #內插搜尋法
# #步驟一 將記錄由小到大的順序給予1,2,3....n的編號
# #步驟二 low=1 , high=n
# #步驟三 當low<high 時,重複執行步驟4與步驟5
# #步驟四 令Mid=low+((key-data[low]))/((data[high-data[low]]))*(high - low)
# #步驟五 若key<key mid 且 high ≠ Mid-1則令high=Mid-1
# #步驟六 若key=key mid 表示成功搜尋到健值的位置
# #步驟七 若key>key mid 且 low ≠ Mid+1 則令 low=Mid+1
#(有些問題待解)
# import random
# def interpolation_search(data,val):
# low=0
# high=49
# print('搜尋處理中.....')
# while low<= high and val !=-1:
# mid=low+int((val-data[low])*(high-low)/(data[high]-data[low])) #內插法公式
# if val==data[mid]:
# return mid
# elif val < data[mid]:
# print('%d 介於位置 %d[%3d] 及中間值 %d[%3d] ,找左半邊 ' \
# %(val,low+1,data[low],mid+1,data[mid]))
# high=mid-1
# elif val > data[mid]:
# print('%d 介於中間值位置 %d[%3d] 及 %d[%3d] ,找右半邊 ' \
# %(val,mid+1,data[mid],high+1,data[high]))
# low=mid+1
# return -1
# val=1
# data=[0]*50
# for i in range(50):
# data[i]=val
# val=val+random.randint(1,5)
# while True:
# num=0
# val=int(input('請輸入搜尋關鍵值(1-150), 輸入-1結束: '))
# if val==-1:
# break
# num=interpolation_search(data,val)
# if num==-1:
# print('### 沒有找到[%3d] ###' %val)
# else:
# print('在第 %2d 個位置找到 [%3d]' %(num+1,data[num]))
# print(' 資料內容:')
# for i in range(5):
# for j in range(10):
# print('%3d-%-3d' %(i*10+j+1,data[i*10+j]),end='')
# print()
已邀請的邦友 {{ invite_list.length }}/5
首先我們必須要先理解使用的時機，以及特徵。內插搜尋法基本上是二元搜尋法的變種，所以特徵上其實差不多
接下來分析的你程式碼
val=1
data=[0]*150
for i in range(50):
data[i]=val
val=val+random.randint(1,5)
1.資料鍵入：你這邊是在輸入你要準備搜尋的資料對吧，你採取用random的方式填寫資料不一定會產出68，這是最重要的一點。注意注意注意注意注意
2.排序：有，由小到大。
OK所以資料檢查方面，第一點會有大問題。
因此我把你的資料改成
data = [1, 3, 6, 8, 12, 13, 17, 22, 24, 27, 32, 37, 40, 42, 44, 46, 49, 51, 56, 61, 68, 69, 70, 74, 77, 81, 86, 88, 91, 96, 100, 102, 105, 106, 109, 110, 111, 114, 117, 119, 121, 126, 131, 136, 139, 144, 148, 151, 152, 156]
然後就沒有問題了....
後就沒有問題了....
就沒有問題了....
簡單來說你就是查尋的資料有問題啦.....
所以我再把你輸入的地方稍微做個修改
val=1
data=[0]*50 #建造50個空間，沒有用到150個空間就不要用這麼多
for i in range(50):#在50個空間裡面塞入隨便的資料，由小到大
data[i]=val
val=val+random.randint(1,5)
print(data)#檢查一下資料狀況，我就是print之後就知道問題可能在哪
while True:
num=0
val=int(input('請輸入搜尋關鍵值(1-%d), 輸入-1結束: '%(data[-1])))
#最大值不一定是150別忘了你建立了50筆資料，夠賽的話最大值250都可以，所以我修成這樣....
最後我在想你可能還有一個地方看不懂
"68 介於中間值位置 24[ 67] 及 50[148] ,找右半邊"
為什麼會print出這樣的提示
24跟50是索引值多1(你程式碼這樣寫的)
67是在第24個位置上的值
148是在第50個位置上的值
以上就這樣，不懂再問吧
後來發現到中間寫法有些問題
你原本的寫法只有以下這樣
mid=low+int((val-data[low])*(high-low)/(data[high]-data[low]))
這樣寫因為
在low=mid-1 || high = mid+1時
都可能會造成val已經不在範圍內了
所以會有兩種狀況發生
if val<data[low] or val>data[high]:#不合理狀況，邊界已經框不到我要查找的值
return -1
mid=low+int((val-data[low])*(high-low)/(data[high]-data[low]))
話說
我會建議改成
while low< high and val !=-1:
要不然可能會造成ZeroDivisionError
iThome鐵人賽
看影片追技術