二分法python上机实验报告_二分查找-Python刷题笔记
二分搜索是一種在有序數(shù)組中查找某一特定元素的搜索算法。
二分查找示意圖
搜索過(guò)程從數(shù)組的中間元素開(kāi)始，如果中間元素正好是要查找的元素，則搜索過(guò)程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開(kāi)始一樣從中間元素開(kāi)始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。
查找特定元素
利用遞歸實(shí)現(xiàn)
# 返回 x 在 arr 中的索引，如果不存在返回 -1
def binarySearch (arr,l,r, x):
# 基本判斷
if r >= l:
mid = l + (h-l)//2 # 中部
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
else:
return binarySearch(arr, mid+1, r, x)
else:
return False
# 測(cè)試
arr = [ 2, 3, 4, 10, 40 ]
x = 10
result = binarySearch(arr,0,len(arr)-1, x)
if result:
print ("元素在數(shù)組中的索引為 %d" % result )
else:
print ("元素不在數(shù)組中")
循環(huán)實(shí)現(xiàn)
def binarySearch(arr, target):
low,high = 0,len(arr)-1
while low <= high:
mid = low + (high - low) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
high = mid - 1
else:
low = mid + 1
return -1
arr = [ 2, 3, 4, 10, 40 ]
x = 10
result = binarySearch(arr, x)
if result:
print ("元素在數(shù)組中的索引為 %d" % result )
else:
print ("元素不在數(shù)組中")
把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱(chēng)之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如，數(shù)組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。
示例 1：
輸入：[3,4,5,1,2]
輸出：1
class Solution:
def minArray(self, numbers: List[int]) -> int:
l, r = 0, len(numbers)-1
while l <= r:
mid = (l+r)//2
if numbers[mid] > numbers[r]:
l = mid + 1
elif numbers[mid] < numbers[r]:
r = mid
else:
r -= 1
return numbers[l]
image
numbers[mid] > numbers[r]
mid 目前處于左排序數(shù)組。也就是說(shuō)旋轉(zhuǎn)點(diǎn)在mid右側(cè)的區(qū)間 [mid+1, r]
numbers[mid] < numbers[r]
mid 目前處于右排序數(shù)組 ，即旋轉(zhuǎn)點(diǎn)一定在mid左側(cè)的區(qū)間 [l, m]
numbers[mid] = numbers[r]
判斷不了mid位置
[1, 0, 1, 1, 1]：旋轉(zhuǎn)點(diǎn) x = 1 ，m=2 在 右排序數(shù)組 中。
[1, 1, 1, 0, 1]：旋轉(zhuǎn)點(diǎn) x = 3 ，m=2 在 左排序數(shù)組 中。
r -= 1 縮小范圍
假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。
( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。
搜索一個(gè)給定的目標(biāo)值，如果數(shù)組中存在這個(gè)目標(biāo)值，則返回它的索引，否則返回 -1 。
你可以假設(shè)數(shù)組中不存在重復(fù)的元素。
你的算法時(shí)間復(fù)雜度必須是 O(log n) 級(jí)別。
找到中點(diǎn)值 MID， 它的左側(cè)或者右側(cè)必有一側(cè)為有序數(shù)列。
# 假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。
# ( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。
# 搜索一個(gè)給定的目標(biāo)值，如果數(shù)組中存在這個(gè)目標(biāo)值，則返回它的索引，否則返回 -1 。
# 你可以假設(shè)數(shù)組中不存在重復(fù)的元素。
# 你的算法時(shí)間復(fù)雜度必須是 O(log n) 級(jí)別。
def search(nums, target):
numslength = len(nums)
l,h = 0, numslength
while l
m = (l+h)//2
if nums[m] == target:
return m
elif nums[m] < target:
if nums[l] == target:
return l
elif nums[l] < nums[m]: # 左側(cè)有序,不在左側(cè)
l = m + 1
elif nums[l] > nums[m]: # 左側(cè)無(wú)序，右側(cè)有序
if target < nums[l]:
l = m + 1
elif target > nums[l]:
h = m - 1
elif nums[m] > target:
if nums[l] == target:
return l
elif nums[l] < nums[m]: # 左側(cè)有序,在左側(cè)
if target < nums[l]:
l = m + 1
elif target > nums[l]:
h = m
elif nums[l] > nums[m]: # 左側(cè)無(wú)序，右側(cè)有序
h = m - 1
return -1
x = search([4,5,6,7,0,1,2],3)
print(x)
超時(shí)
優(yōu)化，合并判斷條件
def search(nums, target):
l,h = 0, len(nums)
while l
m = (l+h)//2
if nums[m] == target:
return m
elif nums[l] == target:
return l
elif nums[m] < target:
if target > nums[l] > nums[m]:
h = m
else:
l = m + 1
elif nums[m] > target:
if target < nums[l] < nums[m]:
l = m + 1
else:
h = m
return -1
x = search([4,5,6,7,0,1,2],3)
print(x)
交互式問(wèn)題
給你一個(gè) 山脈數(shù)組 mountainArr，請(qǐng)你返回能夠使得 mountainArr.get(index) 等于 target 最小 的下標(biāo) index 值。
如果不存在這樣的下標(biāo) index，就請(qǐng)返回 -1。
A.length >= 3
0 < i < A.length - 1 條件下
A[0] < A[1] < ... A[i-1] < A[i]
A[i] > A[i+1] > ... > A[A.length - 1]
# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
# def get(self, index: int) -> int:
# def length(self) -> int:
class Solution:
def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
arr_len = mountain_arr.length()
l,r = 0, arr_len-1
mount_peak_index = 0
# 找峰頂 mount_peak_index
while l < r:
m = (l+r) // 2
ml_val = mountain_arr.get(m-1)
mr_val = mountain_arr.get(m+1)
m_val = mountain_arr.get(m)
if ml_val < m_val and mr_val < m_val:
mount_peak_index = m
break
elif ml_val < m_val < mr_val:
l = m
elif ml_val > m_val > mr_val:
r = m
# 要找等于 target 最小的下標(biāo), 先查左側(cè)
# 峰頂左側(cè)，遞增序列二分查找
l,r = 0,mount_peak_index
while l <= r:
m = (l+r) // 2
m_val = mountain_arr.get(m)
if m_val == target:
return m
elif m_val > target:
r = m-1
elif m_val < target:
l = m+1
# 峰頂右側(cè)，遞減序列二分查找
l,r = mount_peak_index,arr_len-1
while l <= r:
m = (l+r) // 2
m_val = mountain_arr.get(m)
if m_val == target:
return m
elif m_val > target:
l = m+1
elif m_val < target:
r = m-1
return -1
Reference
總結(jié)
以上是生活随笔為你收集整理的二分法python上机实验报告_二分查找-Python刷题笔记的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： C语言中的位域 bit field [转
- 下一篇： ARP协议是什么？