二分探索は意外と難しいと『珠玉のプログラミング』に書いていたので、実際書いてみました。
#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年だったそうです。