介紹
二分查找顧名思義就是從序列的中間位置查找北救，都將目標(biāo)數(shù)字與序列的中間位置數(shù)字進(jìn)行對比臀叙，如果目標(biāo)數(shù)字等于中間位置數(shù)字則返回對應(yīng)的序列索引坐梯，如果目標(biāo)數(shù)字大于中間位置數(shù)字，則繼續(xù)從有側(cè)的序列中利用二分查找森瘪，如果目標(biāo)數(shù)字小于中間位置數(shù)字牡属，則繼續(xù)從左側(cè)的序列中利用二分查找，直到查到目標(biāo)數(shù)字為止扼睬。二分法查找的效率很高逮栅，但是也有其局限性，比如窗宇，目標(biāo)序列必須是有序的序列措伐，查找的目標(biāo)如果在序列中有多個，只能查找到一個等军俊。
這里介紹了基礎(chǔ)的二分查找算法侥加，并且對其進(jìn)行了簡單的擴(kuò)展，擴(kuò)展后增加：
- 容錯功能粪躬，當(dāng)傳參不符合要求的時候不會拋出異常
- 查全功能担败，可以查到目標(biāo)序列中全部的目標(biāo)數(shù)字的位置
- 無序序列處理，如果序列為無序序列時镰官，可以選擇是做普通查找還是轉(zhuǎn)換為有序序列后做二分查找
- 結(jié)果格式化提前，返回結(jié)果為一個字典
1、基礎(chǔ)的二分查找
說明
baseList 必須為有序的數(shù)字序列
targetNum 必須為數(shù)字
如果查找到目標(biāo)數(shù)字則返回對應(yīng)的索引泳唠，如果沒查找到則返回-1
傳參類型錯誤時會拋出異常
源碼
# 二分法查找目標(biāo)數(shù)字狈网，baseList必須為有序的數(shù)字序列（列表或元組）
def halfSearchTargetNum(baseList, targetNum):
leftIndex = 0
rightIndex = len(baseList) - 1
while leftIndex <= rightIndex:
midIndex = int((leftIndex + rightIndex) / 2)
if baseList[midIndex] < targetNum:
leftIndex = midIndex + 1
elif baseList[midIndex] > targetNum:
rightIndex = midIndex - 1
else:
return midIndex
return -1
調(diào)試
if __name__ == '__main__':
test = [-20, -3, 1, 3, 5, 5, 6, 7.6, 8, 56]
print('結(jié)果1：', halfSearchTargetNum(test, 5))
print('結(jié)果2：', halfSearchTargetNum(test, 7.6))
print('結(jié)果3：', halfSearchTargetNum(test, 56))
print('結(jié)果4：', halfSearchTargetNum(test, -20))
print('結(jié)果5：', halfSearchTargetNum(test, 9))
結(jié)果
結(jié)果1: 4
結(jié)果2: 7
結(jié)果3: 9
結(jié)果4: 0
結(jié)果5: -1
2、二分查找算法擴(kuò)展
代碼中有詳細(xì)的注釋說明警检，擴(kuò)展后增加的內(nèi)容包括：
- 容錯功能孙援，當(dāng)傳參不符合要求的時候不會拋出異常
- 查全功能，可以查到目標(biāo)序列中全部的目標(biāo)數(shù)字的位置
- 無序序列處理扇雕，如果序列為無序序列時拓售，可以選擇是做普通查找還是轉(zhuǎn)換為有序序列后做二分查找
- 結(jié)果格式化，返回結(jié)果為一個字典
源碼
# 擴(kuò)展二分法查找數(shù)字镶奉，返回為一個字典
def halfSearchTargetNum(baseList, targetNum, isSorted=False):
# 參數(shù)說明：
# baseList 目標(biāo)序列
# targetNum 目標(biāo)數(shù)字
# isSorted 默認(rèn)為False础淤，如果目標(biāo)序列不是有序序列時，若為False做普通查找哨苛，若為True則排序后做二分查找
targetIndexList = []
res = {'查找結(jié)果': targetIndexList, '目標(biāo)序列': baseList, '目標(biāo)數(shù)字': targetNum, '說明': ''}
# 處理baseList類型錯誤的情況
if not isinstance(baseList, (list, tuple)):
res['說明'] = 'baseList不是列表或元組'
return res
# 處理baseList元素類型錯誤的情況
for item in baseList:
if not isinstance(item, (int, float)):
res['說明'] = 'baseList中有非數(shù)字元素'
return res
# 處理targetNum類型錯誤的情況
if not isinstance(targetNum, (int, float)):
res['說明'] = '目標(biāo)數(shù)字targetNum不是數(shù)字類型'
return res
# 處理targetNum不在baseList的情況
if targetNum not in baseList:
res['說明'] = '目標(biāo)數(shù)字在目標(biāo)序列中不存在'
return res
res['說明'] = '有序序列鸽凶，二分查找'
# 處理baseList不是有序序列的情況
baseListSorted = sorted(baseList)
if baseList != baseListSorted:
# isSorted = True時對目標(biāo)序列重新排序，再對排序后的序列做二分查找
if isSorted:
baseList = baseListSorted
res['原序列'] = res['目標(biāo)序列']
res['目標(biāo)序列'] = baseList
res['說明'] = '無序序列轉(zhuǎn)有序序列建峭，二分查找'
# isSorted = False時不重新排序玻侥，做普通查找
else:
for i in range(0, len(baseList)):
if baseList[i] == targetNum:
targetIndexList.append(i)
res['說明'] = '無序序列，普通查找'
return res
# 開始二分查找
leftIndex = 0
rightIndex = len(baseList) - 1
while leftIndex <= rightIndex:
midIndex = int((leftIndex + rightIndex) / 2)
if baseList[midIndex] < targetNum:
leftIndex = midIndex + 1
elif baseList[midIndex] > targetNum:
rightIndex = midIndex - 1
else:
# 二分查找到的結(jié)果存入列表中
targetIndexList.append(midIndex)
# 在二分查找結(jié)果右側(cè)繼續(xù)查找是否還有目標(biāo)數(shù)字亿蒸，若有就存進(jìn)列表中凑兰，如果遇到不等于目標(biāo)數(shù)字的立即結(jié)束查找（因?yàn)槭怯行虻恼谱覐淖笸也檎遥? for i in range(midIndex + 1, rightIndex + 1):
if baseList[i] != targetNum:
break
else:
targetIndexList.append(i)
# 在二分查找結(jié)果左側(cè)繼續(xù)查找是否還有目標(biāo)數(shù)字，若有就存進(jìn)列表中姑食，如果遇到不等于目標(biāo)數(shù)字的立即結(jié)束查找（因?yàn)槭怯行虻牟ǖ海覐挠彝蟛檎遥? while leftIndex < midIndex:
if baseList[midIndex - 1] != targetNum:
break
else:
targetIndexList.append(midIndex - 1)
midIndex -= 1
# 將結(jié)果列表變?yōu)橛行蛄斜? targetIndexList.sort()
return res
調(diào)試
if __name__ == '__main__':
test1 = [5, 5.1, 5.1, 5.1, 5.11]
test2 = [-20, -3, 92, 12, -2, 12, 7.6, 8, 56]
test3 = 99
test4 = [-20, -3, 92, 12, -2, '12', 7.6, 8, 56]
print('結(jié)果1：',halfSearchTargetNum(test1, 5.1))
print('結(jié)果2：',halfSearchTargetNum(test1, 5.1, isSorted=True))
print('結(jié)果3：',halfSearchTargetNum(test2, 12, isSorted=True))
print('結(jié)果4：',halfSearchTargetNum(test2, 12))
print('結(jié)果5：',halfSearchTargetNum(test2, 100))
print('結(jié)果6：',halfSearchTargetNum(test2, '12'))
print('結(jié)果7：',halfSearchTargetNum(test3, 99))
print('結(jié)果8：',halfSearchTargetNum(test4, 12))
結(jié)果
結(jié)果1： {'查找結(jié)果': [1, 2, 3], '目標(biāo)序列': [5, 5.1, 5.1, 5.1, 5.11], '目標(biāo)數(shù)字': 5.1, '說明': '有序序列，二分查找'}
結(jié)果2： {'查找結(jié)果': [1, 2, 3], '目標(biāo)序列': [5, 5.1, 5.1, 5.1, 5.11], '目標(biāo)數(shù)字': 5.1, '說明': '有序序列音半，二分查找'}
結(jié)果3： {'查找結(jié)果': [5, 6], '目標(biāo)序列': [-20, -3, -2, 7.6, 8, 12, 12, 56, 92], '目標(biāo)數(shù)字': 12, '說明': '無序序列轉(zhuǎn)有序序列则拷，二分查找', '原序列': [-20, -3, 92, 12, -2, 12, 7.6, 8, 56]}
結(jié)果4： {'查找結(jié)果': [3, 5], '目標(biāo)序列': [-20, -3, 92, 12, -2, 12, 7.6, 8, 56], '目標(biāo)數(shù)字': 12, '說明': '無序序列，普通查找'}
結(jié)果5： {'查找結(jié)果': [], '目標(biāo)序列': [-20, -3, 92, 12, -2, 12, 7.6, 8, 56], '目標(biāo)數(shù)字': 100, '說明': '目標(biāo)數(shù)字在目標(biāo)序列中不存在'}
結(jié)果6： {'查找結(jié)果': [], '目標(biāo)序列': [-20, -3, 92, 12, -2, 12, 7.6, 8, 56], '目標(biāo)數(shù)字': '12', '說明': '目標(biāo)數(shù)字不是數(shù)字類型'}
結(jié)果7： {'查找結(jié)果': [], '目標(biāo)序列': 99, '目標(biāo)數(shù)字': 99, '說明': '目標(biāo)序列不是列表或元組'}
結(jié)果8： {'查找結(jié)果': [], '目標(biāo)序列': [-20, -3, 92, 12, -2, '12', 7.6, 8, 56], '目標(biāo)數(shù)字': 12, '說明': '目標(biāo)序列中有非數(shù)字元素'}
