当给定一个数组，要想到一些点：

1、是否已排序

2、是否有重复数字

3、是否有负数

一：常规二分搜索

def bi_search_iter(alist, item):
    left, right = 0, len(alist) - 1
    while left <= right:
        mid = (left + right) // 2
        if alist[mid] < item:
            left = mid + 1
        elif alist[mid] > item:
            right = mid - 1
        else: # alist[mid] = item
            return mid
    return -1

二：二分搜索模板

def binarysearch(alist, item):
    if len(alist) == 0:
        return -1
    
    left, right = 0, len(alist) - 1
    while left + 1 < right:
        mid = left + (right - left) // 2
        if alist[mid] == item:
            right = mid
        elif alist[mid] < item:
            left = mid
        elif alist[mid] > item:
            right = mid
    
    if alist[left] == item:
        return left
    if alist[right] == item:
        return right
    
    return -1

三、在旋转数列中寻找最小值　　

题：假设一个升序排列的数组在某个未知节点处被前后调换，请找到数列中的最小值。

def searchlazy(alist):
    alist.sort()
    return alist[0]

def searchslow(alist):
    mmin = alist[0]
    for i in alist:
        mmin = min(mmin, i)
    return mmin 
        

def search(alist):
    if len(alist) == 0:
        return -1    
    left, right = 0, len(alist) - 1
    while left + 1 < right: 
        if (alist[left] < alist[right]):
            return alist[left];
        mid = left + (right - left) // 2
        if (alist[mid] >= alist[left]):
            left = mid + 1
        else:
            right = mid
    return alist[left] if alist[left] < alist[right] else alist[right]

四、在旋转数组中查找某数

def search(alist, target):
    if len(alist) == 0:
        return -1    
    left, right = 0, len(alist) - 1
    while left + 1 < right: 
        mid = left + (right - left) // 2
        if alist[mid] == target:
            return mid
        
        if (alist[left] < alist[mid]):
            if alist[left] <= target and target <= alist[mid]:
                right = mid
            else:
                left = mid
        else:
            if alist[mid] <= target and target <= alist[right]:
                left = mid
            else: 
                right = mid
                            
    if alist[left] == target:
        return left
    if alist[right] == target:
        return right
        
    return -1

五、搜索插入位置

题：给定一有序数组和一目标值，如果在数组中找到此目标值，返回index，否则返回插入位置。注，可假设无重复元素。

def search_insert_position(alist, target):
    if len(alist) == 0:
        return 0  
    left, right = 0, len(alist) - 1
    while left + 1 < right: 
        mid = left + (right - left) // 2
        if alist[mid] == target:
            return mid
        
        if (alist[mid] < target):
            left = mid
        else:
            right = mid
            
    if alist[left] >= target:
        return left
    if alist[right] >= target:
        return right
        
    return right + 1

六、搜索一个区间

题：找到一个目标值的开始和结束位置

def search_range(alist, target):
    if len(alist) == 0:
        return (-1, -1)  
    
    lbound, rbound = -1, -1

    # search for left bound 
    left, right = 0, len(alist) - 1
    while left + 1 < right: 
        mid = left + (right - left) // 2
        if alist[mid] == target:
            right = mid
        elif (alist[mid] < target):
            left = mid
        else:
            right = mid
            
    if alist[left] == target:
        lbound = left
    elif alist[right] == target:
        lbound = right
    else:
        return (-1, -1)

    # search for right bound 
    left, right = 0, len(alist) - 1        
    while left + 1 < right: 
        mid = left + (right - left) // 2
        if alist[mid] == target:
            left = mid
        elif (alist[mid] < target):
            left = mid
        else:
            right = mid
            
    if alist[right] == target:
        rbound = right
    elif alist[left] == target:
        rbound = left
    else:
        return (-1, -1)        
        
    return (lbound, rbound)

七、在用空字符串隔开的字符串的有序列中查找

题：给定一个有序的字符串序列，这个序列中的字符串用空字符隔开，请写出找到给定字符串位置的方法

def search_empty(alist, target):
    if len(alist) == 0:
        return -1
      
    left, right = 0, len(alist) - 1
    
    while left + 1 < right:
        while left + 1 < right and alist[right] == "":
            right -= 1
        if alist[right] == "":
            right -= 1
        if right < left:
            return -1
        
        mid = left + (right - left) // 2
        while alist[mid] == "":
            mid += 1
            
        if alist[mid] == target:
            return mid
        if alist[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    if alist[left] == target:
        return left
    if alist[right] == target:
        return right    
        
    return -1 

八、在无限序列中找到某元素的第一个出现位置

题：数据流，无限长度中寻找某元素第一个出现位置

def search_first(alist):
    left, right = 0, 1
    
    while alist[right] == 0:
        left = right
        right *= 2
        
        if (right > len(alist)):
            right = len(alist) - 1
            break
    
    return left + search_range(alist[left:right+1], 1)[0]