Bagaimana untuk melaksanakan algoritma carian binari menggunakan java

Cara menggunakan Java untuk melaksanakan algoritma carian binari

Algoritma carian binari ialah kaedah carian yang cekap sesuai untuk tatasusunan yang disusun. Idea asasnya ialah untuk terus menyempitkan julat carian, membandingkan nilai carian dengan unsur-unsur di tengah tatasusunan dan memutuskan sama ada untuk meneruskan mencari separuh kiri atau separuh kanan berdasarkan hasil perbandingan sehingga elemen sasaran ditemui atau julat carian dikurangkan kepada kosong.

Mari perkenalkan secara terperinci cara melaksanakan algoritma carian binari dalam Java.

Langkah 1: Laksanakan kaedah carian binari

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1; //表示未找到目标元素
    }
}

Langkah 2: Uji kaedah carian binari

public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; //已排序数组
        int target = 12; //要查找的目标元素
        int index = BinarySearch.binarySearch(arr, target);
        
        if (index != -1) {
            System.out.println("目标元素在数组中的位置为：" + index);
        } else {
            System.out.println("未找到目标元素");
        }
    }
}

Kod di atas terlebih dahulu mentakrifkan a BinarySearch kelas, yang mengandungi kaedah statik binarySearch untuk melaksanakan algoritma carian binari. Dalam kaedah binarySearch, kami mentakrifkan dua penunjuk, kiri dan kanan, masing-masing untuk menunjuk ke elemen paling kiri dan paling kanan julat carian. Dalam gelung, indeks elemen tengah mid dikira dan kemudian nilai carian dibandingkan dengan arr[mid]. Jika kedua-duanya sama, ini bermakna elemen sasaran ditemui dan nilai indeksnya mid dikembalikan. Jika nilai carian lebih besar daripada arr[mid], gerakkan penunjuk kiri satu kedudukan ke kanan dan sempitkan julat carian ke separuh kanan. Jika nilai carian kurang daripada arr[mid], gerakkan penunjuk kanan satu kedudukan ke kiri dan sempitkan julat carian ke separuh kiri. Gelung berterusan sehingga elemen sasaran ditemui atau julat carian kosong. Jika elemen sasaran tidak ditemui selepas gelung berakhir, -1 dikembalikan untuk menunjukkan bahawa ia tidak ditemui. BinarySearch类，其中包含了一个静态方法binarySearch用于实现二分查找算法。在binarySearch方法中，我们定义了left和right两个指针分别指向查找范围的最左和最右元素。在一个循环中，通过计算得到中间元素的索引mid，然后将查找值与arr[mid]进行比较。如果两者相等，则表示找到了目标元素，返回其索引值mid。如果查找值大于arr[mid]，则将left指针右移一位，缩小查找范围为右半部分。如果查找值小于arr[mid]，则将right指针左移一位，缩小查找范围为左半部分。循环继续直到找到目标元素或查找范围为空。如果循环结束后未找到目标元素，返回-1表示未找到。

在Main类的main方法中，我们创建了一个已排序的数组arr和一个待查找的目标元素target。然后调用BinarySearch类的binarySearch方法进行二分查找，将返回的结果存储在index

Dalam kaedah utama kelas Utama, kami mencipta tatasusunan tersusun arr dan bakal- dicari Elemen sasaran sasaran. Kemudian panggil kaedah binarySearch kelas BinarySearch untuk melakukan carian binari dan simpan hasil yang dikembalikan dalam pembolehubah index. Akhir sekali, ia dinilai sama ada elemen sasaran ditemui berdasarkan hasil yang dikembalikan, dan hasil yang sepadan dicetak.

Melalui contoh kod di atas, kita dapat melihat bahawa melaksanakan algoritma carian binari dalam Java adalah sangat mudah dan hanya memerlukan beberapa baris kod untuk diselesaikan. Kaedah ini mempunyai kerumitan masa carian O(logn), yang sangat cekap dan sesuai untuk tatasusunan diisih yang besar. Jika berbilang operasi carian diperlukan, operasi pengisihan tatasusunan boleh dibahagikan secara berasingan untuk meningkatkan kecekapan.

Saya harap artikel ini akan membantu anda memahami dan menggunakan algoritma carian binari! #🎜🎜#

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma carian binari menggunakan java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!