Menguasai Carian Binari dalam JavaScript dan Java: Panduan Langkah demi Langkah

Carian binari ialah algoritma asas yang harus difahami oleh setiap pembangun, menawarkan cara yang sangat cekap untuk mencari elemen dalam tatasusunan tersusun. Algoritma ini bergantung pada pendekatan "bahagi dan takluk", membolehkannya mengurangkan separuh ruang carian dengan setiap langkah. Dalam artikel ini, kami akan meneroka carian binari dalam JavaScript dan Java, meliputi pelaksanaan berulang dan rekursif.

Apakah Carian Binari?

Carian binari ialah algoritma yang direka untuk mencari kedudukan nilai sasaran dalam tatasusunan yang diisih. Dengan memanfaatkan sifat disusun tatasusunan, carian binari dengan cekap mengecilkan ruang carian, mencapai kerumitan masa O(log n). Ini jauh lebih pantas daripada carian linear dalam set data yang besar.

Berikut ialah gambaran keseluruhan peringkat tinggi:

1. Mulakan dengan dua penunjuk, startIndex dan endIndex, mewakili julat carian semasa.
2. Kira indeks tengah (midIndex) antara startIndex dan endIndex.
3. Bandingkan elemen tengah dengan sasaran:
   • Jika ia sepadan dengan sasaran, kembalikan indeks.
   • Jika elemen tengah lebih besar daripada sasaran, sasaran mestilah di bahagian kiri, jadi laraskan endIndex.
   • Jika elemen tengah kurang daripada sasaran, sasaran mesti berada di separuh kanan, jadi laraskan startIndex.
4. Ulang proses sehingga sasaran ditemui atau startIndex mengatasi endIndex, menunjukkan sasaran tiada dalam tatasusunan.

Mari kita menyelami contoh kod.

Carian Binari Berulang dalam JavaScript dan Java

Pelaksanaan JavaScript

Dalam JavaScript, pendekatan berulang menggunakan gelung untuk melakukan carian binari. Begini rupanya:

const binarySearch = (arr, target) => {
  let startIndex = 0;
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);

    if (arr[midIndex] === target) {
      return midIndex; // Target found
    } else if (arr[midIndex] < target) {
      startIndex = midIndex + 1; // Search in the right half
    } else {
      endIndex = midIndex - 1; // Search in the left half
    }
  }
  return -1; // Target not found
};

let nums = [-1, 0, 3, 5, 9, 12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

Pelaksanaan Java

Di Java, pelaksanaan lelaran agak serupa, dengan pelarasan untuk sintaks Java:

public class BinarySearchExample {

    public static int binarySearch(int[] arr, int target) {
        int startIndex = 0;
        int endIndex = arr.length - 1;

        while (startIndex <= endIndex) {
            int midIndex = (startIndex + endIndex) / 2;

            if (arr[midIndex] == target) {
                return midIndex; // Target found
            } else if (arr[midIndex] < target) {
                startIndex = midIndex + 1; // Search in the right half
            } else {
                endIndex = midIndex - 1; // Search in the left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;

        int result = binarySearch(nums, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

Penjelasan

Dalam kedua-dua pelaksanaan:

• Kami menetapkan startIndex dan endIndex masing-masing pada permulaan dan akhir tatasusunan.
• Setiap lelaran mencari indeks tengah, midIndex dan membandingkan arr[midIndex] dengan sasaran.
  • Jika arr[midIndex] sama dengan sasaran, kami mengembalikan midIndex.
  • Jika arr[midIndex] kurang daripada sasaran, kami mengalihkan startIndex ke midIndex 1, mengecilkan carian ke separuh kanan.
  • Jika arr[midIndex] lebih besar daripada sasaran, kami mengalihkan endIndex ke midIndex - 1, mengecilkan carian ke separuh kiri.
• Gelung keluar jika startIndex melebihi endIndex, bermakna sasaran tiada dalam tatasusunan.

Carian Binari Rekursif dalam JavaScript dan Java

Untuk pendekatan rekursif, kami mentakrifkan fungsi supaya ia memanggil dirinya sendiri dengan indeks yang dikemas kini sehingga sasaran ditemui atau julat carian kosong.

Pelaksanaan JavaScript

Dalam JavaScript, berikut ialah pelaksanaan carian binari rekursif:

const binarySearch = (arr, target) => {
  let startIndex = 0;
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);

    if (arr[midIndex] === target) {
      return midIndex; // Target found
    } else if (arr[midIndex] < target) {
      startIndex = midIndex + 1; // Search in the right half
    } else {
      endIndex = midIndex - 1; // Search in the left half
    }
  }
  return -1; // Target not found
};

let nums = [-1, 0, 3, 5, 9, 12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

Pelaksanaan Java

Di Java, carian binari rekursif yang serupa boleh dilaksanakan seperti berikut:

public class BinarySearchExample {

    public static int binarySearch(int[] arr, int target) {
        int startIndex = 0;
        int endIndex = arr.length - 1;

        while (startIndex <= endIndex) {
            int midIndex = (startIndex + endIndex) / 2;

            if (arr[midIndex] == target) {
                return midIndex; // Target found
            } else if (arr[midIndex] < target) {
                startIndex = midIndex + 1; // Search in the right half
            } else {
                endIndex = midIndex - 1; // Search in the left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;

        int result = binarySearch(nums, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

Cara Versi Rekursif Berfungsi

Dalam setiap panggilan rekursif:

• Indeks tengah, midIndex, dikira.
• Jika arr[midIndex] sepadan dengan sasaran, ia mengembalikan indeks.
• Jika arr[midIndex] lebih besar daripada sasaran, carian diteruskan di bahagian kiri (endIndex menjadi midIndex - 1).
• Jika arr[midIndex] kurang daripada sasaran, carian diteruskan pada separuh kanan (startIndex menjadi midIndex 1).
• Kes asas if (startIndex > endIndex) memastikan rekursi berhenti jika sasaran tidak ditemui.

  ---

  Analisis Kerumitan

  • Kerumitan Masa: Kedua-dua versi lelaran dan rekursif mempunyai kerumitan masa O(log n), kerana setiap langkah mengurangkan separuh ruang carian.
  • Kerumitan Angkasa: Pendekatan berulang ialah O(1) untuk ruang, manakala pendekatan rekursif mempunyai kerumitan ruang O(log n) disebabkan timbunan panggilan.

  Bila Menggunakan Carian Binari

  Carian binari sesuai apabila:

  • Tatasusunan diisih: Carian binari hanya berfungsi pada tatasusunan yang diisih.
  • Kecekapan adalah kritikal: Kerumitan masa O(log n)nya sangat cekap untuk set data yang besar.

  Jika tatasusunan tidak diisih, pertimbangkan untuk mengisihnya dahulu (dengan kos O(n log n)) atau menggunakan carian linear jika set data adalah kecil.

  ---

  Kesimpulan

  Carian binari ialah algoritma yang serba boleh dan cekap untuk mencari elemen dalam tatasusunan yang diisih. Sama ada anda memilih pendekatan berulang atau rekursif, memahami carian binari adalah berharga untuk meningkatkan prestasi aplikasi anda. Cuba kedua-dua pelaksanaan dalam JavaScript dan Java untuk merasai cara ia berfungsi dan lihat yang paling sesuai untuk kes penggunaan khusus anda.

  ---

  ? Rujukan

  • Carian Binari
  • Algoritma Grookking
  • Notasi O Besar

  ? Bercakap dengan saya

  • LinkedIn
  • Github
  • Portfolio

  Atas ialah kandungan terperinci Menguasai Carian Binari dalam JavaScript dan Java: Panduan Langkah demi Langkah. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!