にぶたんについて

二分探索が話題になってたので二分探について書いてみる。

kujira16.hateblo.jp

この記事を見て、二分探の形は人それぞれだと感じた。
自分の二分探はこんな感じです。

    #include <iostream>
    #include <vector>
    using namespace std;
     
    // find を超える最初の要素のインデックスを返す. vは昇順にソートされている.
    int my_upper_bound(vector<int> & v, int find) {
    	int right, left;
    	int res = -1; // 見つからない場合の戻り値
    	left = 0; right = (int)v.size()-1;
    	while(left <= right) {
    		int middle = (left + right) / 2;
     
    		if(find < v[middle]) {
    			// v[middle] は find を超える要素である. (答えの区間)
    			res = middle;
    			right = middle-1;
    		}
    		else {
    			// v[middle] は find 以下の要素である.
    			left = middle+1;
    		}
    	}
    	return res;
    }
     
    int main() {
    	// 引数の生成
    	vector<int> v;
    	for(int i = 0; i < 100; i++) {
    		v.push_back(i);
    	}
    	int res, find;
    	cin >> find;
     
    	res = my_upper_bound(v,find);
    	cout << "my_upper_bound(v," << find << ") returned : " << res << endl;
    	cout << "v[" << res << "] : " << v[res] << endl;
    	return 0;
    }

こういう感じの区間があって、

二分探をはじめる。
もし、middleの指してる要素が答えでなければ、middleの右のほうにleftを移動させる。

もし、middleの指してる要素が答えであれば、答えを仮の変数に格納して(ここ重要)middleの左のほうにrightを移動させる。

区間を狭めながら探索するだけ。left <= rightの間繰り返せばいい。

繰り返しごとに区間が狭まることは明らかな気がする。
二分探書いて無限ループにはまることが多かったのでこの書き方気に入ってます。

あと、for文使ってナントカ回まわす二分探も思いついたので書いて貼っておきます。
実装してたらバグらせた。辛かった。たぶんこんな感じのはず。

#include <iostream>
#include <vector>
using namespace std;

int my_upper_bound(vector<int> & v, int find) {
	int res = -1;
	int tmp = 0, i = 0;
	// 探索する範囲のサイズの二進表現で1の立っている最上位のビットを探索.
	while((int)v.size() > (1 << (i+1))-1) i++;
	// 区間を狭めながら二分探
	for(; i >= 0; i--) {
		if(((tmp | (1 << i)) < v.size())) {
			// middle の代わりが tmp | (1 << i) となる.
			if(find < v[tmp | (1 << i)]) {
				// 条件が成立しているならば答えを仮置き.
				// さらに左の区間を探索するので,tmpはいじらない.
				res = tmp | (1 << i);
			}
			else {
				// そうでないなら,右の区間を探索するようにする.
				tmp |= 1 << i;
			}
		}
	}
	// for文の最後の繰り返しで, 最下位ビットに1を立てて条件が満たされたケース対策.
	return (find < v[tmp]) ? tmp : res;
}

int main() {
	vector<int> v;
	for(int i = 0; i < 100; i++) {
		v.push_back(i);
	}
	int res, find;
	cin >> find;

	res = my_upper_bound(v,find);
	cout << "my_upper_bound(v," << find << ") returned : " << res << endl;
	cout << "v[" << res << "] : " << v[res] << endl;
	return 0;
}