Blog#125: バイナリサーチ：データを見つける最も効率的な方法

この記事の主な目的は、日本語レベルを上げるのを手伝うことです。ソフトウェア開発に関連する概念や知識なとを紹介するために簡単な日本語を使います。ITの知識に関しては、インターネット上でもっとよく説明されているかもしれませんが、この記事の主な目標はまだ日本語を学ぶことです。

---

こんにちは、私はトゥアンと申します。東京からフルスタックWeb開発者です。 将来の有用で面白い記事を見逃さないように、私のブログをフォローしてください。

あなたは今まで、すばやく簡単に何かを見つけたいと思ったことはありますか？バイナリサーチというのは、項目のリストの中からすばやく何かを見つける方法です。宝探しのようなものですが、手がかりの代わりに数字を使います！

バイナリサーチとはどのように機能しますか？

バイナリサーチは、アイテムのリストを半分に分けることで動作します。そして、リストの中央の数字を見ます。もしその数字が探している数字なら、見つけました！でも、もしその数字が探している数字でないなら、リストを再び半分に分けて、中央の数字を見ます。探している数字を見つけるまで、これを繰り返します。

どんなコードでバイナリサーチをするの？

「numbers」という数字のリストがあって、こんな感じです：

[1, 2, 4, 6, 8, 10, 12, 14, 16, 18]

これは、Javascriptで書かれたバイナリサーチのシンプルな例です。

function binarySearch(numbers, target) {
  // Set the start and end of our search
  let start = 0;
  let end = numbers.length - 1;
  
  // Keep searching until we find the target
  while (start <= end) {
    // Find the middle of our search
    let middle = Math.floor((start + end) / 2);
    
    // Check if the middle is the target
    if (numbers[middle] === target) {
      return middle;
    }
    
    // If the middle is not the target, then 
    // check if it is greater or less than 
    // the target and adjust our search accordingly
    if (numbers[middle] < target) {
      start = middle + 1;
    } else {
      end = middle - 1;
    }
  }
  
  // If we don't find the target, then return -1
  return -1;
}

試してみよう！

今、バイナリサーチの仕組みがわかったので、自分で試してみませんか？ 上のコードを使って、数字のリストから8を見つける例を見てみましょう。

let numbers = [1, 2, 4, 6, 8, 10, 12, 14, 16, 18];
let target = 8;

let index = binarySearch(numbers, target);

console.log(index); // 4

8の番号は4番目です。つまり、リストの5番目の数字なんです！

他の例

// An array of words in a dictionary, sorted alphabetically
const dictionaryWords = [
  { index: 1, word: "book" },
  { index: 3, word: "computer" },
  { index: 7, word: "dictionary" },
  { index: 9, word: "elephant" },
  { index: 80, word: "flower" },
];

function binarySearch(list, item, filterCondition = (e) => e) {
  // Get the middle item of the list
  const middle = Math.floor(list.length / 2);
  const middleItem = filterCondition(list[middle]);

  // If the item is the middle item, return it
  if (item === middleItem) {
    return list[middle];
  }

  // If the item is less than the middle item, search the first half of the list
  if (item < middleItem) {
    return binarySearch(list.slice(0, middle), item, filterCondition);
  }

  // If the item is greater than the middle item, search the second half of the list
  if (item > middleItem) {
    return binarySearch(list.slice(middle + 1), item, filterCondition);
  }

  // If the item is not found, return -1
  return -1;
}

const word = binarySearch(dictionaryWords, 3, (e) => e.index);
console.log(word); // { index: 7, word: 'dictionary' }

まとめ

バイナリサーチは、アイテムのリスト内で何かをすばやく見つけるのに最適な方法です。それは速くて効率的で、多くの異なるタイプの問題を解決するのに使用できます。バイナリサーチの仕組みを知った今、ぜひ試してみませんか？

最後

いつもお世話になっています。この記事を楽しんで、新しいことを学べたら嬉しいです。

今度の記事でお会いしましょう！この記事が気に入ったら、私を応援するために「LIKE」を押して登録してください。ありがとうございました。

---

この記事の主な目的は、日本語レベルを上げるのを手伝うことです。ソフトウェア開発に関連する概念や知識なとを紹介するために簡単な日本語を使います。ITの知識に関しては、インターネット上でもっとよく説明されているかもしれませんが、この記事の主な目標はまだ日本語を学ぶことです。