STL 二分查找

很多情况是可以直接使用C++ STL 库中的 lower_bound(), upper_bound() 来方便使用，不过这种方式只满足对于普通数组，而对于结构体或类进行二分时我们就需要自己来完成对复杂结构的二分查找，提高我们程序的运行效率 。

#include "bits/stdc++.h"

using namespace std;

// 模拟 STL的 lower_bound(); 
int* lower_bound(int arr[], int l, int r, int val) { //  注意区间范围 [l, r)
	
	while (l < r) {
		
		int mid = (l + r) / 2;
		if(arr[mid] < val) {
			l = mid + 1;
		}
		else {
			r = mid;
		}
		
	}
	
		return (arr + l);
}

int* upper_bound(int arr[], int l, int r, int val) { //  注意区间范围 [l, r)
	
	while (l < r) {
		
		int mid = (l + r) / 2;
		if(arr[mid] <= val) {
			l = mid + 1;
		}
		else {
			r = mid;
		}
		
	}
	
	return (arr + l);
}

int binary_search(int arr[], int l, int r, int val) { // 区间范围 [l, r)
	
	r = r - 1;
	// 此时 [l, r]
	while(l <= r) { // 此时 l == r 也需要考虑
		int mid = (l + r) / 2;
		if(arr[mid] < val) {
			l = mid + 1;
		}
		else if(arr[mid] > val) {
			r = mid - 1;
		}
		else return mid;
	}
	
	return -1; // 未找到
}

int _binary_search(int arr[], int l, int r, int val) { 
	// 区间范围 [l, r)
	while(l < r) { //[l, r), l == r 时 区间已经无效
		int mid = (l + r) / 2;
		if(arr[mid] < val) {
			l = mid + 1;
		}
		else if(arr[mid] > val) {
			r = mid;
		}
		else return mid;
	}
	
	return -1; // 未找到
}

int main() {
			//   0, 1, 2, 3, 4, 5, 6, 7,   8, 9
	int arr[] = {1, 2, 4, 5, 6, 7, 7, 33, 34, 354};
	
	int idx1 = lower_bound(arr, 1, 10, 6) - arr;
	int idx2 = upper_bound(arr, 1, 10, 7) - arr;
	cout<