尋找數(shù)組變化

給定數(shù)組arr = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1]，返回第一個1的下標(biāo)

很明顯需要借助于二分查找，二分查找輕微變形就可以實現(xiàn)

第一種思路：二分查找，把數(shù)組分成3個部分，left,mid,right,判斷mid是否滿足要求，是的話，直接退出，否的話處理一邊，這個是完全的二分查找的思路

遞歸實現(xiàn)如下：

def binarySearch(arr,left,right):if left < right:mid = left + (right - left ) //2if arr[mid] == 0:# 這個是遞歸的出口之一if arr[mid +1] == 1:return mid + 1else:return binarySearch(arr,mid +1,right)else:# 這個是遞歸的出口之一if arr[mid -1] == 0:return midelse:return binarySearch(arr,left,mid-1)

迭代實現(xiàn)如下：

def binarySearchRecursive(arr):left =0right = len(arr) -1if arr[0] == 1 or arr[-1] == 0 or not arr:return -1# 不會出現(xiàn)left =right,因為在這之前，已經(jīng)找到了，提前退出了# 循環(huán)體條件，有一種形式靠break退出循環(huán)while left < right:# 取中位數(shù)mid = left + (right - left ) //2# 中位數(shù)為0，判斷一下，01直接退出，00的話處理右邊if arr[mid] == 0:if arr[mid +1] == 1:index = mid + 1breakelse:left = mid +1 # 中位數(shù)為1，判斷一下，01的話退出，11的話處理左邊else:if arr[mid -1] == 0:index = midbreakelse:right = mid-1return index

另外一種思路，我們需要找第一個1，實際上我們是需要尋找的是第一個01，假如一般的切的話，就可能把01給切開了，怎么辦？就是不把01切開，假如我們切到mid的是1，那么我們把mid放在和左邊一起，假如我們切到的mid是0，那么我們把mid和右邊放在一起，那么最后找到的兩個元素就一定是01。這樣處理代碼比較簡單，但是假如我們一刀已經(jīng)切到了我們需要找到的那個1的位置，我們竟然沒認(rèn)出來，然后把他又放了進(jìn)去，再去找，在最后只剩下2個元素才找到。

# 還有一種思路mid = left + (right - left ) //2 # arr[mid] =0是處理[mid-1:right] # arr[mid] =1 時處理[left:mid+1] # 這個的含義就是:剩下處理的數(shù)組里總是含有0和1，最后剩余2個時，就是01 def binarySearch2(arr,left,right):if left + 1 == right:index = rightelse:mid = left + (right - left ) //2if arr[mid] == 0:index = binarySearch(arr,mid,right)else:index = binarySearch(arr,left,mid)return index

代碼測試：

arr = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1] left =0 right = len(arr)-1 print(binarySearch(arr,left,right)) print(binarySearchRecursive(arr)) print(binarySearch2(arr,left,right))runfile('D:/share/test/binary_search.py', wdir='D:/share/test') 14 14 14

總結(jié)

以上是生活随笔為你收集整理的寻找数组变化：树形结构，分治模型的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。