Berbagi teknologi

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

🔥 个人主页：puisi kosong

Pencarian Biner adalah algoritma pencarian efisien yang cocok untuk menemukan elemen target dengan cepat dalam array yang dipesan. Dibandingkan dengan pencarian linier, kompleksitas waktu pencarian biner adalah O(log n), yang lebih efisien. Artikel ini akan memperkenalkan secara rinci prinsip, implementasi dan penerapan algoritma pencarian biner.

---

1. Prinsip Algoritma

Pencarian biner dengan cepat menemukan elemen target dengan terus mengurangi separuh rentang pencarian. Langkah-langkah dasarnya adalah sebagai berikut:

1. Rentang pencarian awal adalah indeks awal dan indeks akhir array.
2. Hitung indeks perantara.
3. Membandingkan elemen di indeks tengah dengan elemen target.
   • Jika sama, elemen target ditemukan dan indeksnya dikembalikan.
   • Jika elemen target lebih kecil dari elemen di indeks tengah, persempit rentang pencarian ke separuh kiri.
   • Jika elemen target lebih besar daripada elemen di indeks tengah, persempit rentang pencarian ke separuh kanan.
4. Ulangi langkah di atas hingga rentang pencarian kosong atau elemen target ditemukan.

---

2. Implementasi algoritma

Berikut ini adalah implementasi JavaScript dari pencarian biner:

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

1. Pencarian array yang dipesan: Temukan elemen dengan cepat dalam larik terurut.
2. menyelesaikan masalah: Digunakan untuk menyelesaikan masalah algoritmik tertentu yang memerlukan pencarian biner, seperti menemukan elemen puncak dalam array.
3. analisis data: Dalam analisis data, pencarian biner digunakan untuk menemukan lokasi nilai tertentu dengan cepat.

---

4. Optimalisasi dan perluasan

1. Implementasi rekursif: Selain implementasi berulang, pencarian biner juga dapat diimplementasikan secara rekursif.

/**
 * 递归实现二分查找算法
 * @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. Temukan kemunculan pertama atau terakhir dari: Dengan pencarian biner, algoritme dapat diperluas untuk menemukan posisi elemen target pertama atau terakhir dalam larik terurut.

---

5. Ringkasan

Pencarian biner adalah algoritma pencarian efisien yang dapat dengan cepat menemukan elemen target dalam array yang diurutkan dengan terus mengurangi separuh rentang pencarian. Memahami dan menguasai algoritma pencarian biner sangat penting untuk memecahkan banyak masalah praktis dan mengoptimalkan kinerja program. Saya harap artikel ini akan membantu Anda memahami dan menerapkan pencarian biner.

---