二分查找的特点：
- Sorted （单调递增或者递减）
- Bound （存在上下界）
- Accessible by index （能够通过索引进行访问）
下面是一个常用的代码段
left, right = 0, len(array) - 1
while left <= right:
mid = (left + right) / 2
if array[mid] == target:
return result
elif array[mid] < target:
left = mid + 1
else:
right = mid - 1
leetcode-29 sqrt(x) 题目要求
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
注意事项：
- 在计算时，是需要向下取整的，所以不能仅仅通过比较阈值来确定平方根；
- 由于题目本身的特殊性，大多数的开方是小于这个数的二分之一，所以在这里用了一个res 来保存左边界的值。
class Solution:
def mySqrt(self, x: int) -> int:
left, right = 1, x
res = 0
while left<= right:
mid = (left + right) // 2
if mid == x // mid :
return mid
elif mid > x //mid :
right = mid - 1
elif mid < x// mid :
left = mid+1
res = mid
return res
