読者です 読者をやめる 読者になる 読者になる

二分探索

二分探索は意外と難しいと『珠玉のプログラミング』に書いていたので、実際書いてみました。

#include <iostream>

using namespace std;

int sorted_array[10] = { //テスト用に適当なソート済みデータをでっちあげ
	-1,0,1,2,3,4,5,6,7,8
};

struct BinarySearchError{
};

struct BinarySearchIdxError : public BinarySearchError{
	BinarySearchIdxError(int li_, int ri_) : BinarySearchError(), li(li_), ri(ri_) {}
	~BinarySearchIdxError(){}

	int li, ri;
};


int binary_search(int arr[], int trg, int li, int ri){
	if(li > ri){
		throw BinarySearchIdxError(li, ri);
	}

	int idx = (li + ri) / 2;
	if(arr[idx] == trg){
		return idx;
	}
	else if(li == ri){
		return -1;
	}

	if(arr[idx] < trg){
		li = idx + 1;
	}
	else{//(arr[idx] > trg)
		ri = idx - 1;
	}

	return binary_search(arr, trg, li, ri);
}

int main(){
	try{
		//テスト用の値がちゃんと見つかるかテスト
		for(int i = -1; i < 8; i++){
			int ret = binary_search(sorted_array, i, 0, 9);
			cout << i << " : " << ret << endl;
		}
	}
	catch(BinarySearchIdxError e){
		cout << "インデックスの大小がおかしいです。お手数ですが、ご自分で直してください。" << endl;
		cout << "ちなみに、li -> " << e.li << " で、 ri -> " << e.ri << " でした。" << endl;
	}

	return 0;
}

テストは不十分だけど、一応動きました。意外と難しいかも。ちょっと長いコードになっちゃったし。
例外処理は、ほとんど書いたことがなかったので、見よう見まねだったんですが、なんとかなったかも。

ちなみに二分探索考え方が提示されたのは1946年だったにもかかわらず、バグなしのプログラムができたのは16年後の1962年だったそうです。