:::info 用二分去查找元素
要求数组的有序性或者拥有类似于有序的性质
二分不一定要有单调性，二分的本质是寻找某种性质的分界点。只要可以找到某种性质，使得区间的前半部分满足，后半部分不满足，那么就可以用二分把这个分界点找到。 :::

一、mid = l + r + 1 >> 1 的+1问题

因为 l + r 是下取整，所以如果 l = r - 1，那么mid = l，模板二的更新是l = mid = l，陷入了死循环

  1. int bsearch_2(int l, int r)
  2. {
  3.     while (l < r)
  4.     {
  5.         int mid = l + r + 1 >> 1;
  6.         if (check(mid)) l = mid;
  7.         else r = mid - 1;
  8.     }
  9.     return l;
  10. }

二、代码

这个代码包含两个模板
第一个循环求的是比k大的下标最小的数
第二个循环求的是比k小的下标最大的数

  1. import java.util.Scanner;
  3. public class Main{
  4.     public static void main(String[] args) {
  5.         Scanner in = new Scanner(System.in);
  6.         int n = in.nextInt();
  7.         int[] q = new int[1000];
  8.         for (int i = 0; i < n; i++) {
  9.             q[i] = in.nextInt();
  10.         }
  11.         int k = in.nextInt();
  13.         int l = 0, r = n-1;
  14.         while(l<r){
  15.             int mid = l + r >> 1;
  16.             if (q[mid] >= k) {
  17.                 r = mid ;
  18.             } else {
  19.                 l = mid + 1;
  20.             }
  21.         }
  22.         System.out.println(l + " "+ r);
  23.         l = 0;r = n-1;
  24.         while(l<r) {
  25.             int mid = l + r + 1 >> 1;
  26.             if (q[mid] <= k) {
  27.                 l = mid ;
  28.             } else {
  29.                 r = mid - 1;
  30.             }
  31.         }
  32.         System.out.println(l + " " + r);
  33.     }
  34. }

三、时间复杂度：O(logn)

假使总共有n个元素，那么二分后每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。
最坏的情况是K次二分之后,每个区间的大小为1,找到想要的元素
令n/2^k=1，
可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn).