1. 二分法（Binary Search）的概念

在一个有序数组或者列表中，如果从第一个数字开始查找暴力查找那么时间效率就很低。假设我们有如下的一个列表。

ol=[5,7,12,25,34,37,38,38,43,46,58,80,92,105]

我们如果要查找这个列表是否含有43。那么需要查9次才能查到。但是如果我们利用二分法，时间效率就会提升。那么什么是二分法呢？ 二分法的思路就是折半搜索。如果中间元素就是我们要找的元素，那么搜索过程结束。如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

2.代码实现

#n is the element we are looking for
#l is the orderd List

def binarySearch(n,l):
    left=0
    right=len(l)-1       #Index begins from 0 to len(lst)-1
    while left<=right:
        m=(left+right)//2
        if l[m]==n:
            return m
        elif l[m]>n:
            right=m-1
        else:
            left=m+1
    return -1

3.拓展应用（Leetcode第69题）

实现int sqrt（int x）。 计算并返回 x 的平方根，其中 x 保证为非负整数。 由于返回类型是整数，因此十进制数字将被截断，并且仅返回结果的整数部分。

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

这道题我们可以利用二分法的思路来解决代码如下:

def mySqrt(n):
    if n<0:
        return -1
    left=0  
    right=n
    while (left<=right):
            m=(left+right)//2
            if (m**2<=n and (m+1)**2>n):
                break
            elif(m**2>n):
                right=m-1
            else:
                left=m+1
    return m