地點：基地

時間：2014.04.01

--------------------------------------------------------------------------

一、概述

用於有序區間的函數有一下三個，每種方法都使用了兩個指針first和last，用於限制元素的域為 [first,last)，注意這裡是半開半閉區間，且這些元素按從小到大的順序排序。

1. bool binary_search(Iterator first,Iterator last,const Item& target);

二分查找目標元素。

Iterator lower_bound(Iterator first,Iterator last,const Item& targrt);

返回的指針指向目標出現在域[first,last)中的指針。如果目標不存在則返回的指針指向第一個比目標大的元素。若果數組的元素都小於目標則返回一個與last指針相等的值。可以看做是可以插入到數列且仍保持數列有序的最左邊的位置。

Iterator upper_bound(Iterator first,Iterator last,const Item&target);

返回的指針指向第一個比目標大的元素，如數組中沒有則返回last指針。可以看成是在目標元素可以插入到數列且保持數列有序的最右的位置。

--------------------------------------------------------------------------

二、實例：

#include
#include
#include
#include
using namespace std;
int main(){
	vector pets;
	pets.push_back("cat");
	pets.push_back("dog");
	pets.push_back("fish");
	pets.push_back("snake");
	pets.push_back("turtle");
	vector::iterator first_dog
		= lower_bound(pets.begin(), pets.end(), "dog");
	vector::iterator after_dog
		= upper_bound(pets.begin(), pets.end(), "dog");
	cout << "lower_bound return value: " << *first_dog << endl;
	cout << "upper_bound return value: " << *after_dog << endl;
	return 0;
}