Condivisione della tecnologia

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

🔥 个人主页：poesia vuota

La ricerca binaria è un efficiente algoritmo di ricerca adatto per individuare rapidamente gli elementi target in array ordinati. Rispetto alla ricerca lineare, la complessità temporale della ricerca binaria è O(log n), che è più efficiente. Questo articolo introdurrà in dettaglio il principio, l'implementazione e l'applicazione dell'algoritmo di ricerca binaria.

---

1. Principio dell'algoritmo

La ricerca binaria individua rapidamente l'elemento di destinazione dimezzando continuamente l'intervallo di ricerca. I passaggi fondamentali sono i seguenti:

1. L'intervallo di ricerca iniziale è l'indice iniziale e l'indice finale dell'array.
2. Calcolare l'indice intermedio.
3. Confronta l'elemento nell'indice centrale con l'elemento di destinazione.
   • Se uguale, viene trovato l'elemento di destinazione e viene restituito il suo indice.
   • Se l'elemento di destinazione è più piccolo dell'elemento nell'indice centrale, restringi l'intervallo di ricerca alla metà sinistra.
   • Se l'elemento di destinazione è più grande dell'elemento nell'indice centrale, restringi l'intervallo di ricerca alla metà destra.
4. Ripetere i passaggi precedenti finché l'intervallo di ricerca non è vuoto o non viene trovato l'elemento di destinazione.

---

2. Implementazione dell'algoritmo

Quella che segue è l'implementazione JavaScript della ricerca binaria:

/**
 * 二分查找算法
 * @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. Scenari applicativi

1. Ricerca ordinata di array: individua rapidamente gli elementi in un array ordinato.
2. risolvere problemi: utilizzato per risolvere alcuni problemi algoritmici che richiedono la ricerca binaria, come la ricerca di elementi di picco in un array.
3. analisi dei dati: Nell'analisi dei dati, la ricerca binaria viene utilizzata per trovare rapidamente la posizione di un valore specifico.

---

4. Ottimizzazione ed espansione

1. Implementazione ricorsiva: Oltre all'implementazione iterativa, la ricerca binaria può essere implementata anche in modo ricorsivo.

/**
 * 递归实现二分查找算法
 * @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. Trova la prima o l'ultima occorrenza di: Con la ricerca binaria, l'algoritmo può essere esteso per trovare la posizione del primo o dell'ultimo elemento di destinazione in un array ordinato.

---

5. Riepilogo

La ricerca binaria è un algoritmo di ricerca efficiente in grado di individuare rapidamente l'elemento di destinazione in un array ordinato dimezzando continuamente l'intervallo di ricerca. Comprendere e padroneggiare l'algoritmo di ricerca binaria è di grande importanza per risolvere molti problemi pratici e ottimizzare le prestazioni del programma. Spero che questo articolo ti aiuti a comprendere e applicare la ricerca binaria.

---