技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

🔥 个人主页：空白の詩

二分探索は、順序付けられた配列内のターゲット要素を迅速に見つけるのに適した効率的な検索アルゴリズムです。線形探索と比較すると、二分探索の時間計算量は O(log n) であり、より効率的です。この記事では、二分探索アルゴリズムの原理、実装、応用について詳しく紹介します。

---

1. アルゴリズム原理

二分探索では、探索範囲を半分に続けて高速に目的の要素を見つけます。基本的な手順は次のとおりです。

1. 初期の検索範囲は、配列の開始インデックスと終了インデックスです。
2. 中間インデックスを計算します。
3. 中間のインデックスにある要素をターゲット要素と比較します。
   • 等しい場合、ターゲット要素が見つかり、そのインデックスが返されます。
   • 対象要素が中央インデックスの要素より小さい場合は、検索範囲を左半分に絞ります。
   • 対象要素が中央インデックスの要素より大きい場合は、検索範囲を右半分に絞ります。
4. 検索範囲が空になるか、目的の要素が見つかるまで、上記の手順を繰り返します。

---

2. アルゴリズムの実装

以下は、バイナリ検索の JavaScript 実装です。

/**
 * 二分查找算法
 * @param {number[]} arr - 有序数组
 * @param {number} target - 目标元素
 * @return {number} - 目标元素的索引，未找到返回 -1
 */
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) {
      return mid; // 找到目标元素
    } else if (arr[mid] < target) {
      left = mid + 1; // 查找右半部分
    } else {
      right = mid - 1; // 查找左半部分
    }
  }

  return -1; // 未找到目标元素
}

// 示例
const arr = [1, 3, 5, 7, 9, 11, 13];
const target = 7;
const index = binarySearch(arr, target);
console.log(index); // 输出: 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

3. 応用シナリオ

1. 順序付けされた配列の検索: 順序付けられた配列内の要素をすばやく見つけます。
2. 問題解決: 配列内のピーク要素の検索など、二分探索を必要とする特定のアルゴリズムの問​​題を解決するために使用されます。
3. データ分析: データ分析では、特定の値の位置をすばやく見つけるために二分探索が使用されます。

---

4. 最適化と拡張

1. 再帰的な実装: 反復実装に加えて、二分探索は再帰的に実装することもできます。

/**
 * 递归实现二分查找算法
 * @param {number[]} arr - 有序数组
 * @param {number} target - 目标元素
 * @param {number} left - 左索引
 * @param {number} right - 右索引
 * @return {number} - 目标元素的索引，未找到返回 -1
 */
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) {
    return -1; // 未找到目标元素
  }

  const mid = Math.floor((left + right) / 2);

  if (arr[mid] === target) {
    return mid; // 找到目标元素
  } else if (arr[mid] < target) {
    return binarySearchRecursive(arr, target, mid + 1, right); // 查找右半部分
  } else {
    return binarySearchRecursive(arr, target, left, mid - 1); // 查找左半部分
  }
}

// 示例
const indexRecursive = binarySearchRecursive(arr, target);
console.log(indexRecursive); // 输出: 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2. 最初または最後の出現を検索します。: 二分探索を使用すると、アルゴリズムを拡張して、順序付けされた配列内の最初または最後のターゲット要素の位置を見つけることができます。

---

5. まとめ

二分探索は、探索範囲を継続的に半分にすることで、順序付けられた配列内の目的の要素を迅速に見つけることができる効率的な探索アルゴリズムです。二分探索アルゴリズムを理解して習得することは、多くの実際的な問題を解決し、プログラムのパフォーマンスを最適化するために非常に重要です。この記事が二分探索の理解と応用に役立つことを願っています。

---