算法精讲【整数二分】（实战教学）

---------------模板讲解---------------

媒介：

    温馨提示：
  

• 本片博客博主主要使用口语化的叙述，缘故起因是：下面的内容大部门是博主的做题的心得领会（声明：“博主不是什么算法大佬，仅仅是一位 靠咖啡续命、靠玄学debug的算法咸鱼，分享这篇博客是为了记录自己的学习心得，如果能帮到同样挣扎的你，那就值回咖啡钱了！"）
  
• 这篇博客也是博主想到哪就写到哪完成的，以是会有写的不当的地方，还请大佬指正
  
• 博客中有一些二分的编程题练习并挂有链接，盼望大家在熟悉了模板之后进行练习加以巩固
  
• 每道编程题博主都有提供博主使用模板AC的代码，供大家参考（博主的代码中有大量的解释，记录了博主思索过程）
  
• 写这篇博客主要是为了:
  
  
  
  • 教算法小白一个常用的算法：二分查找
    
  • 资助算法初学者克服对二分的恐惊
    
  
  

  在这里博主为正在学算法的你打打气：就算AC率感人，我们也要倔强地WA下去！
  

---

  学二分查找的痛点：二分查找的思想虽然简朴，但是却极其容易写出死循环，那有有没有什么方法可以使我们又快又好的写出正确的二分查找呢？
  

---

  深思：出现这种环境的根本缘故起因是二分虽然简朴，但是二分的类型多，且不同种类型的二分的区别并不明显，这就使得我们常常容易搞混，面临具体的问题时一时不知道到底该怎么二分
这里博主将会根据自己的理解重新梳理所有的二分的环境，并尽量的简化模板，方便大家影象。
  

---

  在博主看来二分从形式上有以下四类：
  

   虽然有四种环境，着实我们可以使用一个模板来解决这四种环境
  不说废话了，直接给大家上模板
  温馨提示：
  

• C++代码的部门是直接可以照抄的部门
  
• 伪代码的部门是需要我们根据具体的题意进行随机应变的部门
  

  （下面有讲解应该怎么进行随机应变）

1. //注意：在给binary_search函数传参时，区间端点(l,r)是开区间
2. //例如：你想对区间[1,9]进行二分查找，你应该传入的参数应该是：(l=0,r=10)
3. int binary_search(int l, int r, int 基准值)
4. {
5.         while (l + 1 < r)
6.         {
7.                 int mid = (l + r) >> 1;
8.                 if (待二分数组[mid] </<= 基准值)  l = mid;
9.                 else  r = mid;
10.         }
12.         if (待二分数组[l/r] == 基准值) return l/r; //返回的l/r就是目标值的下标
13.     else return -1;
14. }

复制代码

  应用上面的模板进行二分查找中，只有两个地方需要我们具体环境具体分析：
  随机应变1：binary_search函数中l和r该谁进行更新的if判断该怎么写：
  

• if (待二分数组[mid] 写<还是<= 基准值)
  

  随机应变2：binary_search函数中函数竣事时该返回什么的if判断该怎么写：
  

• if (q[写l还是r] == 基准值) return 返回l还是r;
  

  

---

  疑问：怎样熟练随机应变1？
  第一步：要清楚分界线的位置在哪里？
  第二步：是写<还是<=，就是根据分界线mid左侧的值和基准值之间的关系决定的
  

• 基准值：简朴一点说就是上面的图片中的5
  

  写<或<=总共有2环境：
  

• 写<：对应环境1和环境2
  
• 写<=：对应环境3和环境4
  

  以是：也就是说只要你可以知道这道题属于二分的哪种环境，随机应变1着实也可以照抄。
  

---

  疑问：怎样熟练随机应变2？
  写l/r和返回l/r组合在一起总共有4种环境：
  

• 写r返回l：对应环境1
  
• 写r返回r：对应环境2
  
• 写l返回l：对应环境3
  
• 写l返回r：对应环境4
  

  以是：也就是说只要你可以知道这道题属于哪种环境，随机应变2着实也可以照抄。
  说的有点抽象，我们直接看图片演示 + 代码示例：
  环境1：找到末了一个<3的元素的位置

1. int binary_search(int l, int r, int target)
2. {
3.         while (l + 1 < r)
4.         {
5.                 int mid = (l + r) >> 1;
6.                 if (q[mid] < 3)  l = mid; //随机应变1：写<
7.                 else  r = mid;
8.         }
10.         if (q[r] == 3) return l;// 随机应变2：写r ，返回l
11.         else return -1;
12. }

复制代码

环境2：找到第一个>=3的元素的位置

1. int binary_search(int l, int r, int target)
2. {
3.         while (l + 1 < r)
4.         {
5.                 int mid = (l + r) >> 1;
6.                 if (q[mid] < 3)  l = mid; //随机应变1：写<
7.                 else  r = mid;
8.         }
10.         if (q[r] == 3) return r;// 随机应变2：写r ，返回r
11.         else return -1;
12. }

复制代码

环境3：找到末了一个<=3的元素的位置

1. int binary_search(int l, int r, int target)
2. {
3.         while (l + 1 < r)
4.         {
5.                 int mid = (l + r) >> 1;
6.                 if (q[mid] <= 3)  l = mid; //随机应变1：写<=
7.                 else  r = mid;
8.         }
10.         if (q[l] == 3) return l;// 随机应变2：写l ，返回l
11.         else return -1;
12. }

复制代码

环境4：找到第一个>3的元素的位置

1. int binary_search(int l, int r, int target)
2. {
3.         while (l + 1 < r)
4.         {
5.                 int mid = (l + r) >> 1;
6.                 if (q[mid] <= 3)  l = mid; //随机应变1：写<=
7.                 else  r = mid;
8.         }
10.         if (q[l] == 3) return r;// 随机应变2：写l ，返回r
11.         else return -1;
12. }

复制代码

---------------经典例题---------------

入门经典例题：789.数的范围

   开始挑战： 789.数的范围
  

   如果你已经把握了上面我讲的内容的话，那么我们不丢脸出这道问题所属的二分类型：
  

• 所求元素的起始位置 —> 第2种环境
  
• 所求元素的终止位置 —> 第3种环境
  

1. #include<iostream>
2. #include<algorithm>
3. #include<cstring>
4. using namespace std;
6. const int N = 100010;  
7. int n, q;
8. int arr[N];  
11. //第一个二分查找找的是：被询问数的第一次出现的位置(下标)
12. int binary_search1(int arr[], int len, int x) {
13.     int l = -1, r = len;
14.     while(l + 1 < r)
15.     {
16.         int mid = (l + r) / 2;
17.         if(arr[mid]<x)  l = mid;
18.         else  r = mid;
19.     }
20.     if(arr[r] == x) return r;
21.     else return -1;  //找不到就返回-1
22. }
25. //第二个二分查找找的是：被询问数的最后一次出现的位置(下标)
26. int binary_search2(int arr[], int len, int x) {
27.     int l = -1, r = len;
28.     while(l + 1 < r)
29.     {
30.         int mid = (l + r) / 2;
31.         if(arr[mid]<= x)  l = mid;
32.         else  r = mid;
33.     }
34.     if(arr[l] == x) return l;
35.     else return -1;  //找不到就返回-1
36. }
38. int main()
39. {
40.     scanf("%d %d", &n, &q);
41.     for(int i = 0; i < n; i++)  scanf("%d", &arr[i]);
43.     while(q --)
44.     {
45.         int x;
46.         scanf("%d", &x);
47.         
48.         int res1 = binary_search1(arr, n, x);
49.         int res2 = binary_search2(arr, n, x);
50.         
51.         printf("%d %d\n", res1, res2);
52.     }
53.     return 0;
54. }   

复制代码

  总结：
虽然我们的方法并不高明，甚至在别人看来是愚蠢的写法，为了写这道题还要两个二分查找函数。
但是我们的方法胜在模板固定，仅需稍作修改每种二分环境便都能使用，并且修改的判断也很简朴。
  根本不需要动脑分析什么界限环境，更不会出现死循环的环境，彻底解放