寻找数组变化

给定数组arr = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1]，返回第一个1的下标

很明显需要借助于二分查找，二分查找轻微变形就可以实现

第一种思路：二分查找，把数组分成3个部分，left,mid,right,判断mid是否满足要求，是的话，直接退出，否的话处理一边，这个是完全的二分查找的思路

递归实现如下：

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)

迭代实现如下：

def binarySearchRecursive(arr):left =0right = len(arr) -1if arr[0] == 1 or arr[-1] == 0 or not arr:return -1# 不会出现left =right,因为在这之前，已经找到了，提前退出了# 循环体条件，有一种形式靠break退出循环while left < right:# 取中位数mid = left + (right - left ) //2# 中位数为0，判断一下，01直接退出，00的话处理右边if arr[mid] == 0:if arr[mid +1] == 1:index = mid + 1breakelse:left = mid +1 # 中位数为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。这样处理代码比较简单，但是假如我们一刀已经切到了我们需要找到的那个1的位置，我们竟然没认出来，然后把他又放了进去，再去找，在最后只剩下2个元素才找到。

# 还有一种思路mid = left + (right - left ) //2 # arr[mid] =0是处理[mid-1:right] # arr[mid] =1 时处理[left:mid+1] # 这个的含义就是:剩下处理的数组里总是含有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

总结

以上是生活随笔为你收集整理的寻找数组变化：树形结构，分治模型的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。