二分查找,二分答案 | Axell's Blog

二分法

• 二分查找

  • 确定在有序序列中,第一个满足某一条件的数的位置

• 二分答案：

  • 求满足某一条件的最大/最小值时，对答案区间进行左右划分的算法。

• 题目特征: 求最小(大)值的最大(小)值

• 注意: 一定要小心边界,l,r分别为可能符合的最小/大值,而并非1和n

• 代码:

  int l,r,mid,ans;
  
  l=1;r=n;                    //确定要查找的左右区间
  
  while (l<=r){               //l>r时查找已经完成
      mid=(l+r)/2;            //先确定一个位置
  
      if (......){            //判断是否满足条件
          ans=mid;            //如果满足,传出答案
          [l=mid+1;]
          [r=mid-1;]          //二选一
      }
  
      else{                   //否则重新确定范围
          [r=mid-1;]
          [l=mid+1;]          //二选一
      }
  }
  cout<<ans<<endl;
  

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/20/