二分探索(C++)

code:memo.cpp

#include <iostream>

#include <vector>

using namespace std;

vector<int> a = {1, 14, 32, 51, 51, 51, 243, 419, 750, 910};

// 目的の値 key の index を返すようにする (ない場合は -1)

int binary_search(int key) {

int left = 0, right = (int)a.size() - 1; // 配列 a の左端と右端

while (right >= left) {

int mid = left + (right - left) / 2; // 区間の真ん中

if (amid == key) return mid;

else if (amid > key) right = mid - 1;

else if (amid < key) left = mid + 1;

}

return -1;

}

int main() {

cout << binary_search(51) << endl; // a4 = 51 (他に a3, a5 も)

cout << binary_search(1) << endl; // a0 = 1

cout << binary_search(910) << endl; // a9 = 910

cout << binary_search(52) << endl; // -1

cout << binary_search(0) << endl; // -1

cout << binary_search(911) << endl; // -1

}