Partage de technologie

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

🔥 个人主页：poème vierge

La recherche binaire est un algorithme de recherche efficace adapté pour localiser rapidement des éléments cibles dans des tableaux ordonnés. Par rapport à la recherche linéaire, la complexité temporelle de la recherche binaire est O(log n), ce qui est plus efficace. Cet article présentera en détail le principe, la mise en œuvre et l'application de l'algorithme de recherche binaire.

---

1. Principe de l'algorithme

La recherche binaire localise rapidement l'élément cible en réduisant continuellement de moitié la plage de recherche. Les étapes de base sont les suivantes :

1. La plage de recherche initiale est l'index de début et l'index de fin du tableau.
2. Calculez l'indice intermédiaire.
3. Compare l'élément à l'index du milieu à l'élément cible.
   • S'il est égal, l'élément cible est trouvé et son index est renvoyé.
   • Si l'élément cible est plus petit que l'élément situé à l'index du milieu, réduisez la plage de recherche à la moitié gauche.
   • Si l'élément cible est plus grand que l'élément situé à l'index du milieu, réduisez la plage de recherche à la moitié droite.
4. Répétez les étapes ci-dessus jusqu'à ce que la plage de recherche soit vide ou que l'élément cible soit trouvé.

---

2. Mise en œuvre de l'algorithme

Voici l'implémentation JavaScript de la recherche binaire :

/**
 * 二分查找算法
 * @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. Scénarios d'application

1. Recherche de tableau ordonné: Localisez rapidement les éléments dans un tableau ordonné.
2. résoudre des problèmes: Utilisé pour résoudre certains problèmes algorithmiques qui nécessitent une recherche binaire, comme la recherche d'éléments de pointe dans un tableau.
3. l'analyse des données: Dans l'analyse des données, la recherche binaire est utilisée pour trouver rapidement l'emplacement d'une valeur spécifique.

---

4. Optimisation et expansion

1. Implémentation récursive: En plus de l'implémentation itérative, la recherche binaire peut également être implémentée de manière récursive.

/**
 * 递归实现二分查找算法
 * @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. Rechercher la première ou la dernière occurrence de: Avec la recherche binaire, l'algorithme peut être étendu pour trouver la position du premier ou du dernier élément cible dans un tableau ordonné.

---

5. Résumé

La recherche binaire est un algorithme de recherche efficace qui peut localiser rapidement l'élément cible dans un tableau ordonné en réduisant continuellement de moitié la plage de recherche. Comprendre et maîtriser l'algorithme de recherche binaire est d'une grande importance pour résoudre de nombreux problèmes pratiques et optimiser les performances du programme. J'espère que cet article vous aidera à comprendre et à appliquer la recherche binaire.

---