Membina Carian Tatasusunan Diisih Diputar dalam Java: Memahami Carian Pangsi dan Binari

Apakah Tatasusunan Isih Diputar?

Pertimbangkan tatasusunan yang diisih, sebagai contoh:

[1, 2, 3, 4, 5, 6]

Sekarang, jika tatasusunan ini diputar pada beberapa pangsi, katakan pada indeks 3, ia akan menjadi:

[4, 5, 6, 1, 2, 3]

Perhatikan bahawa tatasusunan masih diisih, tetapi ia dibahagikan kepada dua bahagian. Matlamat kami adalah untuk mencari nilai sasaran dalam tatasusunan sedemikian dengan cekap.

---

Strategi Carian

Untuk mencari dalam tatasusunan diisih yang diputar, kita perlu:

1. Cari Pivot: Pivot ialah titik di mana tatasusunan beralih daripada nilai yang lebih besar kepada nilai yang lebih kecil.
2. Carian Perduaan: Setelah kita menemui pangsi, kita boleh menggunakan carian binari pada separuh tatasusunan yang sesuai.

---

Penjelasan Kod Langkah demi Langkah

class Solution {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 1, 2, 3}; // Example of rotated sorted array
        int target = 5;

        // Searching for the target
        int result = search(arr, target);

        // Displaying the result
        System.out.println("Index of target: " + result);
    }

    // Main search function to find the target in a rotated sorted array
    public static int search(int[] nums, int target) {
        // Step 1: Find the pivot
        int pivot = searchPivot(nums);

        // Step 2: If no pivot, perform regular binary search
        if (pivot == -1) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }

        // Step 3: If the target is at the pivot, return the pivot index
        if (nums[pivot] == target) {
            return pivot;
        }

        // Step 4: Decide which half of the array to search
        if (target >= nums[0]) {
            return binarySearch(nums, target, 0, pivot - 1); // Search left side
        } else {
            return binarySearch(nums, target, pivot + 1, nums.length - 1); // Search right side
        }
    }

    // Binary search helper function
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (arr[mid] == target) {
                return mid; // Target found
            } else if (target < arr[mid]) {
                end = mid - 1; // Search left half
            } else {
                start = mid + 1; // Search right half
            }
        }
        return -1; // Target not found
    }

    // Function to find the pivot index in a rotated sorted array
    static int searchPivot(int[] arr) {
        int start = 0;
        int end = arr.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            // Check if mid is the pivot point
            if (mid < end && arr[mid] > arr[mid + 1]) {
                return mid;
            }

            // Check if the pivot is before the mid
            if (mid > start && arr[mid] < arr[mid - 1]) {
                return mid - 1;
            }

            // Decide whether to move left or right
            if (arr[mid] <= arr[start]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return -1; // No pivot found (array is not rotated)
    }
}

---

Penjelasan Kod

1. cari():

   • Fungsi ini bertanggungjawab untuk mencari sasaran dalam tatasusunan diisih yang diputar.
   • Pertama sekali, kami mencari pangsi menggunakan fungsi searchPivot().
   • Bergantung pada kedudukan pangsi, kami kemudian memutuskan separuh daripada tatasusunan yang hendak dicari menggunakan carian binari.

2. binarySearch():

   • Algoritma carian binari standard untuk mencari sasaran dalam sub-tatasusunan yang diisih.
   • Kami mentakrifkan indeks mula dan tamat serta secara beransur-ansur menyempitkan ruang carian.

3. searchPivot():

   • Fungsi ini mengenal pasti titik pangsi (tempat di mana tatasusunan berputar).
   • Pangsi ialah indeks yang tertib diisih "pecah" (iaitu tatasusunan beralih daripada nilai yang lebih tinggi kepada nilai yang lebih rendah).
   • Jika tiada pangsi ditemui, ini bermakna tatasusunan tidak diputar dan kami boleh melakukan carian binari biasa.

---

Bagaimana Algoritma Berfungsi

Untuk tatasusunan seperti [4, 5, 6, 1, 2, 3]:

• pangsi berada pada indeks 2 (6 ialah yang terbesar, dan ia diikuti dengan 1, yang terkecil).
• Kami menggunakan pangsi ini untuk membahagikan tatasusunan kepada dua bahagian: [4, 5, 6] dan [1, 2, 3].
• Jika sasaran lebih besar daripada atau sama dengan elemen pertama (4 dalam kes ini), kami mencari bahagian kiri. Jika tidak, kami mencari bahagian kanan.

Kaedah ini memastikan kami mencari dengan cekap, mencapai kerumitan masa O(log n), serupa dengan carian binari standard.

---

Kesimpulan

Tatasusunan diisih yang diputar ialah soalan temu bual biasa dan cabaran yang berguna untuk memperdalam pemahaman anda tentang carian binari. Dengan mencari pangsi dan menyesuaikan carian binari kami dengan sewajarnya, kami boleh mencari dengan cekap melalui tatasusunan dalam masa logaritma.

Jika anda mendapati artikel ini membantu, sila hubungi saya di LinkedIn atau kongsi pendapat anda dalam ulasan! Selamat mengekod!

Atas ialah kandungan terperinci Membina Carian Tatasusunan Diisih Diputar dalam Java: Memahami Carian Pangsi dan Binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!