二分查找本身的思路是很简单的，也没有什么弯弯绕绕，什么情况写二分？有序数组+暴力解是一次for循环的情况，基本就是二分的题。有两种写法，左闭右闭，左闭右开。
二分查找的潜规则
- 边界区间规则：循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则
| 左闭右开 ✔ | 左闭右闭 |
|---|---|
l = mid + 1 and r = mid |
l = mid +1 and r = mid -1 |
mid = l + (r - l) // 2 |
mid = l + (r - l) // 2 |
while l < r |
while l <= r |
为什么mid要加一？显然，因为target不等于nums[mid]的值，没必要。
- mid的写法。
一般写成mid = l + (r - l) // 2，c++的题解会写成mid = l + (r - l) / 2，这是语言本身关于类型的特性，重思想轻语言。 - 终止循环要不要加等于号？
还是跟区间设置有关，左闭右开不加等号，左闭右闭加等号。
所以，选择一种写法即可，记住该写法的对应规则。左闭右开的规则下，最终l会和r相等。
1. 给一个递增不重复数组，获取目标在数组中的位置。
# 左闭右开
def binarySearch(nums: list, target: int) -> int:
l = 0
r = len(nums)
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
r = mid
else:
l = mid + 1
return -1
2. 求开方，向下取整。
def sqrt(a: int) -> int:
l = 0
r = a
if a == 0:
return 0
while l < r:
mid = l + (r - l) // 2
if mid * mid == a:
return mid
elif mid * mid > a:
r = mid
else:
l = mid + 1
# 为什么是 l - 1，因为l越过了mid，加了1，本题要求向下取整，所有要具体问题具体分析
return l - 1
3. 统计逆序数组中复数的个数。此题左闭右开不甚好写，真是可恶。
def get_nums(nums:list) -> int:
l = 0
r = len(nums) - 1
count = 0
if nums[r ] > 0:
return -1
while l <= r:
mid = l + (r - l)// 2
if nums[mid] > 0:
l = mid + 1
elif nums[mid] < 0:
r = mid - 1
count = len(nums) - l
return count
