寻找数组变化

给定数组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 ) //2
        
        if arr[mid] == 0:
            # 这个是递归的出口之一
            if arr[mid +1] == 1:
                return mid + 1
            else:
                return binarySearch(arr,mid +1,right)
            
        else:
            # 这个是递归的出口之一
            if arr[mid -1] == 0:
                return mid
            else:
                return binarySearch(arr,left,mid-1)

迭代实现如下：

def binarySearchRecursive(arr):
    left =0
    right = len(arr) -1
    
    if 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 + 1
                break
            else:
                left = mid +1   
        # 中位数为1，判断一下，01的话退出，11的话处理左边
        else:
            if arr[mid -1] == 0:
                index = mid
                break
            else:
                right = mid-1
                
    return 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 = right
        
    else:
        mid = left + (right - left ) //2
        
        if 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