二分法

定义

二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法。

过程

以在一个升序数组中查找一个数为例。

它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

二分查找模板

int L = 1, R = n;
while(L <= R)
{
    int mid = (L + R) / 2;
    if(arr[mid] == x)//如果中间值是x，则结束查找
    {
        cout << mid;
        return 0;
    }
    else if(arr[mid] > x)//如果中间值大于x，则去左边找
    {
        R = mid - 1;
    }
    else//如果中间值小于x，则去右边找
    {
        L = mid + 1;
    }
}

二分查找左侧边界模板

int p = -1;
	int l = 1, r = n;
	while(l <= r)
	{
		int mid = (l + r) / 2;
		if(a[mid] >= x)
		{
			if(a[mid] == x)
			{
				p = mid;
			}
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}