Binary search basis

One 、 Two points search

First , It is clear that the premise of binary search is for ordered arrays , Then the significance of binary search on this basis is to use the order of data structure to simplify the time and space overhead of the algorithm .
in addition , Binary search is the same as double pointer traversal array , But the difference is that binary search moves every time ‘ Half interval ’ length , The double pointer problem moves step by step .

Two 、 classification

The standard of classification here is the method to solve the problem ：

1. The interval is defined as left closed and right closed , The corresponding boundary condition is l<=r, Because when there is only one number left , Still reasonable , for example [5,5], At this time, it is written as ：

int l = 0;
int r = nums.size()-1;
while(l<=r){
    
  mid = (l+r)/2;
...
}

3. The interval is defined as left closed and right open , The corresponding boundary condition is l<r, Because when there is only one number left , unreasonable , for example [5,5）, and [5,6) reasonable , At this time, it is written as ：

int l = 0;
int r = nums.size();
while(l<r){
    
  mid = (l+r)/2;
...
}

Both can solve the problem , But there are some differences in writing , It is suggested to learn one .