算法刷题【二分法】

题目：

• 注意题目中说明了数据时非递减的，那么这样就存在二分性，能够实现logn的复杂度。
• 二分法每次只能取寻找特定的某一个值，所以我们要分别求左端点和有端点。

分析第一组用例得到结果如下:

成功找到左端点8

由此可知，用二分法去寻找左端端点的时候：

• 若num[mid]<target，那么此时mid的左边包括自身的值都小于target,所以直接执行赋值操作left = mid + 1即可。

• 当num[mid]= =target的时候，由于可能此时的mid已经是左端端点了。但是只是可能是左端点了，也有可能不是左端点，所以相等的情况就要和大于的情况合并起来操作，执行right = mid操作。

• 当num[mid]>target的时候，mid的右边包括自身都比target的值要大，执行right = mid具有合理性,不能执行right = mid -1因为此时和等于合并起来了，判断条件变成是num[mid] <= target在等于的情况下，可能成为左端的端点。
  图示*😗
  
  上述就是找最左边的端点的基本思路了，但是我们还有一些细节需要处理:

• 对于每次mid位置的取发:
  1:mid = left + (right-left)/2
2:mid = left + (right-left +1)/2
  有以上两种取法，前后者在奇数的情况下相同，但是在偶数的情况下就会有所不同。
  偶数的情况下，1会取到中间两个数的片左边的那一个，2会取到中间两个数的偏右边那一个。

对于取左边端点来说:

到最终可能会有这么一种的情况:

所以在用二分法寻找左侧端点的时候，应该要使用mid的第一种取法(mid = left + (right-left)/2 )。