Compartir tecnología

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

🔥 个人主页：poema en blanco

La búsqueda binaria es un algoritmo de búsqueda eficiente adecuado para localizar rápidamente elementos de destino en matrices ordenadas. En comparación con la búsqueda lineal, la complejidad temporal de la búsqueda binaria es O (log n), que es más eficiente. Este artículo presentará en detalle el principio, la implementación y la aplicación del algoritmo de búsqueda binaria.

---

1. Principio del algoritmo

La búsqueda binaria localiza rápidamente el elemento objetivo reduciendo continuamente a la mitad el rango de búsqueda. Los pasos básicos son los siguientes:

1. El rango de búsqueda inicial es el índice inicial y el índice final de la matriz.
2. Calcular el índice intermedio.
3. Compara el elemento en el índice medio con el elemento de destino.
   • Si es igual, se encuentra el elemento de destino y se devuelve su índice.
   • Si el elemento de destino es más pequeño que el elemento en el índice medio, limite el rango de búsqueda a la mitad izquierda.
   • Si el elemento de destino es más grande que el elemento en el índice medio, limite el rango de búsqueda a la mitad derecha.
4. Repita los pasos anteriores hasta que el rango de búsqueda esté vacío o se encuentre el elemento de destino.

---

2. Implementación del algoritmo

La siguiente es la implementación JavaScript de la búsqueda 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. Escenarios de aplicación

1. Búsqueda de matriz ordenada: localice rápidamente elementos en una matriz ordenada.
2. resolver problemas: Se utiliza para resolver ciertos problemas algorítmicos que requieren búsqueda binaria, como encontrar elementos máximos en una matriz.
3. análisis de los datos: En el análisis de datos, la búsqueda binaria se utiliza para encontrar rápidamente la ubicación de un valor específico.

---

4. Optimización y expansión

1. Implementación recursiva: Además de la implementación iterativa, la búsqueda binaria también se puede implementar de forma recursiva.

/**
 * 递归实现二分查找算法
 * @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. Encuentre la primera o última aparición de: Con la búsqueda binaria, el algoritmo se puede ampliar para encontrar la posición del primer o último elemento de destino en una matriz ordenada.

---

5. Resumen

La búsqueda binaria es un algoritmo de búsqueda eficiente que puede localizar rápidamente el elemento objetivo en una matriz ordenada reduciendo continuamente a la mitad el rango de búsqueda. Comprender y dominar el algoritmo de búsqueda binaria es de gran importancia para resolver muchos problemas prácticos y optimizar el rendimiento del programa. Espero que este artículo le ayude a comprender y aplicar la búsqueda binaria.

---