Bagaimana untuk menggunakan Advanced Binary Scarch ?

Kenapa dan bagaimana?

semasa saya menyelesaikan soalan pada leetcode yang mengatakan dalam tatasusunan Diberi nombor integer yang diisih dalam susunan tidak menurun, cari kedudukan permulaan dan penamat bagi nilai sasaran yang diberikan. jadi adalah mustahil untuk mengembalikan permulaan dan penamat elemen sasaran dalam tatasusunan dengan scarch binari mudah kerana ia hanya mengembalikan indeks di mana ia menjumpai elemen sasaran pertama yang boleh menjadi apa sahaja yang pertama, akhir atau tengah elemen itu. jadi kami menggunakan Double Binary Scarch , dan inilah cara untuk melakukannya ...

Pendekatan

1. Carian Perduaan Pertama:

   • Lakukan carian binari untuk mencari kejadian terakhir sasaran.
   • Mulakan dengan si (indeks mula) pada 0 dan ei (indeks akhir) pada nums.length - 1.
   • Jika elemen tengah nombor[pertengahan] kurang daripada sasaran, gerakkan indeks mula si ke pertengahan + 1 untuk mencari di separuh kanan.
   • Jika ia lebih besar daripada sasaran, gerakkan indeks akhir ei ke pertengahan - 1 untuk mencari di bahagian kiri.
   • Jika angka[pertengahan] sama dengan sasaran, tetapkan res[1] kepada pertengahan (hujung julat semasa) dan teruskan mencari di separuh kanan (si = pertengahan + 1) untuk mencari kejadian terakhir.

2. Carian Binari Kedua:

   • Lakukan carian binari lain untuk mencari kejadian pertama sasaran.
   • Tetapkan semula si kepada 0 dan ei kepada nums.length - 1.
   • Ikuti pendekatan yang serupa seperti sebelum ini, tetapi jika angka[pertengahan] sama dengan sasaran, tetapkan res[0] kepada pertengahan (permulaan julat semasa) dan teruskan mencari di separuh kiri (ei = pertengahan - 1) hingga cari kejadian pertama.

3. Keputusan Pulangan:

   • Resis tatasusunan hasil mengandungi indeks permulaan dan penamat bagi nilai sasaran.

Kerumitan

• Kerumitan Masa:

  • Pencarian binari untuk kejadian pertama dan terakhir setiap satu mengambil masa O(log n). Memandangkan kami melakukan dua carian binari, kerumitan masa keseluruhan ialah O(log n).

• Kerumitan Angkasa:

  • O(1) kerana kami menggunakan jumlah tetap ruang tambahan untuk pembolehubah.

Kod

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int ei = nums.length - 1;
        int si = 0;
        int[] res = {-1, -1};  // Initialize result array

        // First binary search to find the last occurrence
        while (si <= ei) {
            int mid = si + (ei - si) / 2;
            if (target < nums[mid]) {
                ei = mid - 1;
            } else if (target > nums[mid]) {
                si = mid + 1;
            } else {
                res[1] = mid;  // Update end index
                si = mid + 1;  // Search in the right half
            }
        }

        // Reset the pointers for the second binary search
        si = 0;
        ei = nums.length - 1;

        // Second binary search to find the first occurrence
        while (si <= ei) {
            int mid = si + (ei - si) / 2;
            if (target < nums[mid]) {
                ei = mid - 1;
            } else if (target > nums[mid]) {
                si = mid + 1;
            } else {
                res[0] = mid;  // Update start index
                ei = mid - 1;  // Search in the left half
            }
        }

        return res;  // Return the result array
    }
}

Atas ialah kandungan terperinci Bagaimana untuk menggunakan Advanced Binary Scarch ?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!