二分查找也稱為折半查找，要求查找的對象是順序排列的（從小到大或者從大到?。?，其時間復雜度為O(log2n)，下面是二分查找最簡單的例子：

def binary_search(data_list, val):    
    low = 0                         # 最小數(shù)下標    
    high = len(data_list) - 1       # 最大數(shù)下標    
    while low <= high:        
        mid = (low + high) // 2     # 中間數(shù)下標        
        if data_list[mid] == val:   # 如果中間數(shù)下標等于val, 返回            
            return mid        
        elif data_list[mid] > val:  # 如果val在中間數(shù)左邊, 移動high下標            
            high = mid - 1        
        else:                       # 如果val在中間數(shù)右邊, 移動low下標            
            low = mid + 1    
    return # val不存在, 返回None

二分法可謂是一種非?；镜牟檎曳椒ǎ泻芏鄨鼍岸伎梢允褂玫蕉址ǎ旅嫖覀儊砜匆幌?。

1. 有重復元素的二分法查找

給定一個 元素有序的（升序）整型數(shù)組 nums 和一個目標值 target ，寫一個函數(shù)搜索 nums 中的第一個出現(xiàn)的target，如果目標值存在返回下標，否則返回 -1。

def search(nums , target ):
    res = -1
    if len(nums) < 1:
        return res
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low+ high) // 2
        if nums[mid] == target:
            res = mid
            high = mid - 1   # 與傳統(tǒng)二分法相比，多了該步驟，因為需要查找到第一次出現(xiàn)target元素的位置
        elif nums[mid] > target:
            high = mid - 1
        else:
            low = mid + 1
    return res

2. 求平方根

def sqrt(self , x ):
        if x < 1:
            return 0
        elif x < 4:
            return 1
        l, h = 1, x // 2
        while l <= h:
            mid = (l + h) // 2
            if mid * mid == x:
                return mid
            elif mid * mid < x:
                l = mid + 1
            else:
                h = mid - 1
        return h

3. 旋轉過的有序數(shù)組中尋找目標值

給定一個整數(shù)數(shù)組nums，按升序排序，數(shù)組中的元素各不相同。
nums數(shù)組在傳遞給search函數(shù)之前，會在預先未知的某個下標 t（0 <= t <= nums.length-1）上進行旋轉，讓數(shù)組變?yōu)閇nums[t], nums[t+1], ..., nums[nums.length-1], nums[0], nums[1], ..., nums[t-1]]。
比如，數(shù)組[0,2,4,6,8,10]在下標3處旋轉之后變?yōu)閇6,8,10,0,2,4]
現(xiàn)在給定一個旋轉后的數(shù)組nums和一個整數(shù)target，請你查找這個數(shù)組是不是存在這個target，如果存在，那么返回它的下標，如果不存在，返回-1。

"""
與中間值比較，分前半段有序和后半段有序分別判斷。比有序的二分查找多一些判定條件。
1、 要么前半段有序，要么后半段有序。
2、 當前半段有序時：即循環(huán)數(shù)組中間值比循環(huán)數(shù)組最左邊值大 則 nums[left] <= nums[mid]
當target 比中間值小，比最左值（前半段最小值）大時，肯定在前面部分 則high = mid - 1 。
如果不在前半段，可能在后半段，low = mid + 1。
3、同理后半段也一樣。
ps:分前半段有序后半段有序時，當nums[left] <= nums[mid] 則 left到mid有序。
否則 mid到right 有序。
"""
    def search(self , nums , target ):
        # write code here
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if target == nums[mid]:
                return mid
            if nums[mid] >= nums[l]:
                if (nums[mid] > target):
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] < target:# <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
                    
        return -1