Logicky Blog

Logickyの開発ブログです

二分探索

参考:二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita

コードはC++です。

int binary_search(int ng, int ok, int key) {
  while (abs(ok - ng) > 1) {
    int mid = (ok + ng) / 2;
    if (isOk(mid, key)) ok = mid;
    else ng = mid;
  }
  return ok;
}

20歳以上36歳未満の人の年齢を当てる場合は下記です。

#include <bits/stdc++.h>
using namespace std;

bool isOk(int num, int key) {
  if (num >= key) return true;
  return false;
}

int binary_search(int ng, int ok, int key) {
  while (abs(ok - ng) > 1) {
    int mid = (ok + ng) / 2;
    if (isOk(mid, key)) ok = mid;
    else ng = mid;
  }
  return ok;
}

int main() {
  int min = 20, max = 35;
  int age;
  cin >> age;
  cout << "あなたは" << binary_search(min - 1, max, age) << "才ですね!" << endl;
}