アルゴリズム図解第一章アルゴリズム概要の二分ルックアップC++コード実装

二分ルックアップは、効率の高いルックアップ方法である半角ルックアップ(Binary Search)とも呼ばれます.ただし、半角ルックアップでは、線形テーブルは順序記憶構造を採用する必要があり、テーブル内の要素はキーワード順に並べられています.
これは何も言うことはありません.本ではよく言っています.ここではデフォルトは秩序ある配列です.もし無秩序が検索する前にソートを追加してから検索することができたら、最適なソートアルゴリズムを使えばいいです.ソートアルゴリズムはここでは言いません.また、再帰でも二分検索は実現できますが、スペースがかかりすぎるのでお勧めしません.以下はC++コード実装です.

int BS(vector<int>& a,int key){
	int l=0,r=a.size(),m;
	while(l<=r)
	{
		m=l+(r-l)/2;			//  r+l  
		if(a[m]==key) return m;
		else if(a[m]<key) r=m-1;
		else if(a[m]>key) l=m+1;
	}
	return -1;
}