二分适用于满足二段性的序列，当一个序列中一段满足条件，另一段不满足条件时可以考虑使用二分来加快查找速度

板子

// x 是需要查找的数
int l = 0, r = n - 1;
while (l < r)
{
	int mid = l + r >> 1;
    if (q[mid] >= x) r = mid; // 符号按需要更改
    else l = mid + 1;
}
return r;

符号判断

二分中使用什么符号曾经困扰了我很久，现总结如下：
大原则：搞不清就带等号，带等号的时候和字面理解意思相同
其中，以下两个式子表示含义相同：

  • >= 会输出满足大于等于条件的第一个数
  • < 会输出从后往前看不满足小于条件的第一个数

以下两个式子表示含义相同：

  • <= 会输出从后往前看满足小于等于条件的第一个数
  • > 会输出不满足条件的最后一个数

举个栗子

现有如下序列：1 2 3 4 5 5 5 6 7 8 9

现需查找 “5” ——

  • 当使用 >= 时，找到的是第 1 个 5
  • 当使用 <= 时，找到的是第 3 个 5
  • 当使用 > 时，找到的是第 1 个 5
  • 当使用 < 时，找到的是第 3 个 5