普通情况：
给出一个升序的数组 numnumnum，数组长度为 lenlenlen。补全binary_search函数，判断数组num中是否存在元素target，若存在则返回该数字在数组中的 下标，否则返回 −1-1−1。
min 指向头，max 指向尾，mid 为（min + max) / 2
当min >= max 时候终止循环
如果arr[mid] < target , min = mid + 1;
如果arr[mid] > target , max = mid - 1;
如果arr[mid] == target , 找到结果
int binary_search(int target, int *num, int len) {
int left, right, mid;
left = 0; right = len - 1;
while (left <= right) {
mid = (left + right) >> 1;
if (num[mid] == target) return mid;
if (num[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
在这个查找元素的过程中，为了查找（目的）
首先是left 和 right 的范围 ：也就是数组元素的范围
循环的条件：left <= right ,
也就意味着终止循环后left 一定大于right（终止条件）
缩小范围的方式 : left = mid + 1, right = mid - 1;
因为目的是为了查找，所以嘛，既然mid 不是待查找的，
那么直接不要它就好了，答案绝对不会在mid上出现了，所以果断的不要它。
特殊情况１
前面一堆０后面一堆１，寻找第一个１
对于给定的一个由 000 和 111 组成、且按照 0,0,0,…,0,1,1,…,1,10,0,0,\ldots,0,1,1,\ldots,1,10,0,0,…,0,1,1,…,1,1 的规则排列的数组，从中快速找出第一个 111 的位置。
find_first_1(arr)
left = 0, right = arr.length - 1
while left < right
mid = (left + right) / 2
if arr[mid] == 1
right = mid
else
left = mid + 1
return left
注意这个是为了找到第一个１
首先是left 和 right 的范围 ：
left = 0, right = length(指向最后一个元素的下一个）<mark>处理全0的时候</mark>
为啥不会越界访问呢，因为访问nums 是通过mid来访问的
又因为mid的范围是[0,length - 1]
循环的条件：left < right ,
也就意味着终止循环后left 一定等于right（终止条件）
缩小范围的方式 : left = mid + 1, right = mid ;
因为目的是为了找到第一个１嘛
所以，当nums[mid] == 1 时，right = mid;
因为这个时候无法确定mid所指向的１是不是第一个1，所以不能舍弃
但是 当nums[mid] != 1时，left = mid + 1；
因为这个时候mid指向的是0,一定不是第一个１，所以可以果断舍弃。
特殊情况２
前面一堆１后面一堆０，寻找最后一个１
这个和情况1的考虑类似，
find_last_1(arr)
left = 0, right = arr.length - 1
while left < right
mid = (left + right) / 2 + 1
if arr[mid] == 1
left = mid
else
right = mid - 1
return left
注意这个是为了找到最后一个１
首先是left 和 right 的范围 ：
left = -1, right = lenght - 1（处理全0)
为啥不会越界访问呢，因为访问nums 是通过mid来访问的
mid的范围是[0,length - 1]
循环的条件：left < right ,
也就意味着终止循环后left 一定等于right（终止条件）
缩小范围的方式 : left = mid, right = mid - 1;
因为目的是为了找到第一个１嘛
所以，当nums[mid] == 1 时， left = mid;
因为这个时候无法确定mid所指向的１是不是最后一个1，所以不能舍弃
但是 当nums[mid] != 1时，right = mid - 1；
因为这个时候mid指向的是0,一定不是最后一个１，所以可以果断舍弃。
稍微注意的一点是
当l = r - 1 时，（l + r) / 2 是 l 所以为了避免这个时候的死循环,
mid = (l + r ) / 2 + 1;
总结一下
二分是对单调函数的查找，通过每次缩小一半的问题求解空间来提升效率.
京公网安备 11010502036488号