探索

会社にて。3000件くらいのレコードに対して、毎回全探索している実装があったので、二分探索するように書き直してみた。多分、こんな感じでいいんだよね。

int a[3000];  // 昇順でソート済み

int hoge(int key) {
  int idx;
  int idx1 = 0, idx2 = 2999;

  while (1) {
    idx = (idx1 + idx2) / 2;
    if (a[idx] == key) {
      return idx;
    }
    if (idx1 == idx2) {
      return -1;
    }
    if (a[idx] > key) {
      idx2 = idx;
    } else {
      idx1 = (idx1 + 1 == idx2) ? idx2 : idx;
    }
  }
}

それにしても、もともとの実装のままだと、全部のレコードを探索するのに N*N/2 = 4500000回ですか。これが二分探索になる事で、N*log2(N) = 39000回と、探索回数が1/100以下になるんだよねぇ。全レコードをソートするオーバーヘッドがあるにしても、かなり処理時間の短縮が期待できそう。