二分查找总结——左闭右开区间和左闭右闭区间（C++语言）

二分查找：

1.左闭右开区间，如有相同元素返回查找到的第一个元素。

PS：主循环判断条件都是一样的（left < right），注意这里不能取等号！有相同元素时，如果要返回第一个查找到的元素，则区间包含相同元素时应该从右向左收缩，这时判断条件应该加上等号，并且此时找到的就是第一个元素的秩；如果要返回最后一个查找到的元素，则区间包含相同元素时应该从左向右收缩，这时判断条件没有等号，并且此时找到的是大于目标元素的第一个元素的秩，因此应该返回的目标元素的秩等于找到的秩减一。

#include <iostream>
#include <stdio.h>

using namespace std;

//左闭右开，相同元素返回第一个
int binSearch(int* A, int e, int left, int right)
{
	while (left < right)
	{
		int mid = left + ((right - left) >> 1);   //移位操作比除操作快
		(e <= A[mid]) ? right = mid : left = mid + 1; //从右向左收缩
	} 
	return left;    //找到的就是需要返回的
}

int main()
{
	int A[10] = { 0, 1, 2, 3, 3, 4, 5, 6, 6, 7 };
	int a = binSearch(A, 0, 0, 10);
	int b = binSearch(A, 1, 0, 10);
	int c = binSearch(A, 2, 0, 10);
	int d = binSearch(A,