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

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

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

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

「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' }

まとめ

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

Mình hy vọng bạn thích bài viết này và học thêm được điều gì đó mới.

Donate mình một ly cafe hoặc 1 cây bút bi để mình có thêm động lực cho ra nhiều bài viết hay và chất lượng hơn trong tương lai nhé. À mà nếu bạn có bất kỳ câu hỏi nào thì đừng ngại comment hoặc liên hệ mình qua: Zalo - 0374226770 hoặc Facebook. Mình xin cảm ơn.

Momo: NGUYỄN ANH TUẤN - 0374226770

TPBank: NGUYỄN ANH TUẤN - 0374226770 (hoặc 01681423001)