Temu Duga Pengekodan: Cari Kedudukan Pertama dan Terakhir dengan Carian Perduaan

Masalah dan Konteks yang Berkenaan

Diberikan satu tatasusunan integer nums yang disusun dalam tertib tidak menurun dan satu integer target, kembalikan indeks pertama dan terakhir bagi target. Kembalikan [-1, -1] apabila ia tiada. Tatasusunan mungkin kosong dan mungkin mengandungi duplikasi, dan fungsi tersebut tidak boleh mengubahnya. Kerumitan masa yang diperlukan ialah O(log n) dengan ruang tambahan O(1).

Sebagai contoh, nums = [1, 2, 2, 2, 3] dan target = 2 mengembalikan [1, 3]; target = 4 mengembalikan [-1, -1]. Imbasan linear boleh menghasilkan jawapan tersebut, tetapi kes terburuknya iaitu O(n) melanggar keperluan.

Soalan ini sesuai untuk pusingan pengekodan bagi peranan kejuruteraan perisian dan algoritma. Panduan temu duga SDE II semasa Amazon mengharapkan kod yang betul dari segi sintaksis, berskala, teguh, dan diuji dengan baik, dan LeetCode mengekalkan masalah teras yang sama. Ujian sebenar bukanlah menghafal dua templat. Ia adalah mentakrifkan sempadan carian dengan cukup tepat supaya syarat gelung, kemas kini selang, dan nilai pulangan semuanya mematuhi satu invarian.

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah sama ada calon menyedari bahawa sekadar mencari mana-mana kejadian adalah tidak mencukupi. Carian perduaan biasa yang mengembalikan nilai apabila terdapat persamaan tidak menjamin kejadian paling kiri atau paling kanan. Mencari satu kejadian dan kemudian mengimbas ke luar masih merosot kepada O(n) apabila setiap elemen sama dengan sasaran.

Isyarat kedua ialah semantik sempadan. Penguraian yang bersih mencari dua titik sisipan:

• lowerBound: kedudukan pertama yang nilainya lebih besar daripada atau sama dengan target.
• upperBound: kedudukan pertama yang nilainya lebih besar secara ketat daripada target.

Modul rasmi Python bisect_left dan bisect_right menggunakan takrifan partisi ini. Sebaik sahaja kedua-dua titik adalah betul, sasaran yang wujud menduduki [lowerBound, upperBound - 1].

Isyarat ketiga ialah invarian gelung. Dengan selang separuh terbuka [left, right), tatasusunan kosong secara semula jadi bermula sebagai [0, 0), dan penamatannya ialah left === right. Mencampurkan peraturan selang tertutup dengan pemulaan separuh terbuka, seperti menetapkan right kepada nums.length dan kemudian membaca nums[right], menyebabkan capaian luar batas atau gelung tidak menamat.

Akhir sekali, penemu duga mencari pengesahan. Jawapan yang kukuh merangkumi tatasusunan kosong, satu elemen, semua duplikasi, sasaran di bawah nilai minimum, sasaran di atas nilai maksimum, sasaran di kedua-dua hujung, dan sasaran yang tiada. Ia juga menerangkan sebab target + 1 bukanlah teknik batas atas yang umum: ia bergantung pada pengganti berangka diskret, mencipta nilai luar domain pada integer selamat terbesar, dan tidak boleh dilanjutkan kepada rentetan atau pembanding tersuai.

Soalan Penjelasan Sebelum Menjawab

• Adakah tatasusunan sudah disusun? Gesaan ini menjamin tertib tidak menurun. Menyusun input yang tidak tersusun sambil

mengekalkan indeks asal mengubah model data dan membuang batas jumlah O(log n).

• Adakah kita mengembalikan indeks asal atau yang telah disusun? Ia adalah sama di sini kerana input sudah pun disusun.
• Apakah yang mewakili ketiadaan sasaran? Gesaan ini memerlukan [-1, -1]; titik sisipan bukan secara automatik merupakan padanan.
• Adakah nilai pendua dibenarkan? Ya. Nilai pendua adalah sebab mengapa carian sempadan diperlukan.
• Bolehkah tatasusunan menjadi kosong? Ya. Pelaksanaan separuh terbuka mengendalikannya tanpa membaca mana-mana titik akhir.
• Apakah domain berangka? Nilai adalah integer selamat JavaScript. Penyelesaian ini tidak mengira target + 1, jadi

ia tidak menghasilkan sentinela luar domain semata-mata untuk mencari sempadan.

• Adakah carian perduaan mesti dilaksanakan sendiri? Ya untuk latihan temu duga ini. Dalam pengeluaran, utamakan fungsi

pustaka standard apabila kontraknya sepadan tepat.

• Bolehkah input diubah suai? Tidak, dan kedua-dua carian sempadan tidak perlu mengubahnya.

Rangka Kerja Jawapan 30 Saat

“Saya akan menjalankan dua carian sempadan dan bukannya mencari satu kejadian lalu mengimbas. lowerBound mencari pada selang separuh terbuka [left, right) untuk nilai pertama yang lebih besar daripada atau sama dengan target; upperBound mencari nilai pertama yang lebih besar secara ketat daripada target. Setiap lelaran menggunakan middle = left + floor((right - left) / 2). Jika titik tengah masih berada di sebelah kiri sasaran, tetapkan left = middle + 1; jika tidak, kekalkan titik tengah dengan right = middle. Saya terlebih dahulu memeriksa sama ada batas bawah berada di luar julat atau tidak sama dengan sasaran. Jika ia wujud, jawapannya ialah [lower, upper - 1]. Dua carian kekal O(log n) dengan ruang tambahan O(1).”

Perincian Langkah demi Langkah

Langkah 1: Tulis semula “pertama dan terakhir” sebagai dua titik partisi.

Untuk nums = [1, 2, 2, 2, 3] dan target = 2:

lowerBound = 1  // first nums[i] >= 2
upperBound = 4  // first nums[i] > 2
answer = [1, 4 - 1] = [1, 3]

Takrifan ini lebih mudah disahkan berbanding “terus mencari ke kiri” dan “terus mencari ke kanan.” Titik sisipan kekal bermakna apabila sasaran tiada. Untuk target = 4, kedua-duanya bersamaan dengan panjang tatasusunan 5, tetapi itu tidak bermakna sasaran tersebut wujud. Algoritma mesti menyemak secara berasingan nums[lower] === target.

Langkah 2: Tetapkan invarian selang separuh terbuka.

Pada permulaan setiap lelaran lowerBound:

1. Setiap indeks di bawah left mengandungi nilai yang lebih kecil secara ketat daripada target.
2. Setiap indeks pada atau di atas right mengandungi nilai yang lebih besar daripada atau sama dengan target.
3. Selang calon yang belum diselesaikan ialah [left, right).

Pada mulanya, left = 0 dan right = nums.length; kedua-dua kawasan luar adalah kosong, jadi invarian kekal benar. Jika nums[middle] < target, titik tengah dan segala-galanya di sebelah kirinya tidak mungkin menjadi jawapan, jadi tetapkan left = middle + 1. Jika tidak, titik tengah mungkin merupakan kedudukan sah pertama dan mesti dikekalkan, jadi tetapkan right = middle.

Setiap lelaran memendekkan selang secara ketat. Apabila left === right, tiada elemen yang belum diselesaikan kekal. Segala-galanya di sebelah kiri adalah lebih kecil dan segala-galanya di sebelah kanan adalah lebih besar daripada atau sama dengan sasaran, maka kedudukan ini ialah batas bawah.

upperBound menggunakan struktur yang sama dengan partisi yang berbeza:

1. Setiap indeks di bawah left mengandungi nilai yang kurang daripada atau sama dengan target.
2. Setiap indeks pada atau di atas right mengandungi nilai yang lebih besar secara ketat daripada target.

Oleh itu, ia menggerakkan left apabila nums[middle] <= target dan sebaliknya menggerakkan right.

Langkah 3: Laksanakan kedua-dua fungsi sempadan.

function lowerBound(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const middle = left + Math.floor((right - left) / 2);
    if (nums[middle] < target) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }

  return left;
}

function upperBound(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const middle = left + Math.floor((right - left) / 2);
    if (nums[middle] <= target) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }

  return left;
}

Satu-satunya perbezaan ialah perbandingannya. Dua fungsi yang dinamakan dengan jelas lebih mudah diterangkan dalam temu duga berbanding satu fungsi dengan suis Boolean legap, dan ia mengelakkan daripada mencipta abstraksi generik yang kompleks untuk satu kegunaan sahaja.

Titik tengah ialah left + floor((right - left) / 2), jadi ia tidak menambah dua indeks besar terlebih dahulu. Had tatasusunan masa jalanan JavaScript menjadikan limpahan indeks tidak mungkin berlaku dalam konteks ini, tetapi ungkapan ini boleh dipindahkan dengan selamat ke bahasa berinteger lebar tetap.

Langkah 4: Gabungkan keputusan dan sahkan padanan sebenar.

function searchRange(nums: number[], target: number): [number, number] {
  const first = lowerBound(nums, target);

  if (first === nums.length || nums[first] !== target) {
    return [-1, -1];
  }

  return [first, upperBound(nums, target) - 1];
}

Urutan semakan adalah penting. Uji first === nums.length sebelum membaca nums[first], supaya kedudukan selepas tatasusunan tidak dianggap sebagai satu elemen. Sebaik sahaja first diketahui sepadan, batas atas adalah sekurang-kurangnya first + 1, dan menolak satu daripadanya memberikan kejadian terakhir.

Jangan gantikan batas atas dengan lowerBound(nums, target + 1) - 1. Di bawah kekangan safe-integer gesaan ini, pendekatan tersebut mungkin masih mengembalikan sempadan yang betul, tetapi menambah satu kepada Number.MAX_SAFE_INTEGER meninggalkan domain di mana aritmetik integer tepat dijamin. Jika input berkembang kepada sebarang Number JavaScript, integer bersebelahan juga boleh runtuh di bawah kejituan titik terapung. Rentetan, nilai BigInt, dan pembanding tersuai tidak mempunyai “nilai seterusnya” yang universal. Mencari terus nilai pertama yang lebih besar secara ketat daripada sasaran menyatakan keseluruhan kontrak.

Langkah 5: Buktikan kerumitan.

Setiap gelung mengurangkan selang calon dengan panjang k kepada paling banyak kira-kira k / 2, jadi setiap fungsi sempadan melakukan O(log n) perbandingan. Dua carian masih kekal O(log n). Algoritma ini hanya menyimpan bilangan indeks yang malar, menggunakan ruang tambahan O(1), dan tidak mengubah suai tatasusunan.

Mencari mana-mana kejadian dan mengimbas ke luar melawat semua n elemen untuk [2, 2, ..., 2], menghasilkan kes terburuk O(n). Jadual cincangan pra-kiraan boleh menjadikan carian berulang pantas, tetapi pembinaannya memerlukan masa dan ruang O(n). Ia hanya berguna untuk banyak pertanyaan ke atas input statik yang sama dan mengabaikan kelebihan tertib tersusun yang diberikan.

Langkah 6: Sahkan dengan kes sempadan dan ujian pembezaan rawak.

Sekurang-kurangnya, rangkumi:

Kemudian jana tatasusunan tersusun dengan duplikasi dan bandingkan hasilnya dengan garis dasar linear indexOf dan lastIndexOf. Pendekatan linear tidak memenuhi sasaran kerumitan, tetapi ia adalah oracle ujian yang sangat baik. Kes tetap memeriksa sempadan yang diketahui, manakala ujian pembezaan rawak mendedahkan ralat yang berkaitan dengan kiraan duplikasi atau titik akhir tertentu.

Contoh Jawapan Berkualiti Tinggi

“Tatasusunan sudah pun disusun dan keperluannya ialah O(log n), jadi saya tidak akan mencari satu sasaran lalu mengimbas ke luar; tatasusunan yang kesemuanya duplikasi akan menjadi linear. Saya mentakrifkan jawapan dengan dua titik sisipan: nilai pertama yang lebih besar daripada atau sama dengan sasaran, dan nilai pertama yang lebih besar secara ketat daripada sasaran.

Kedua-dua carian menggunakan selang separuh terbuka [left, right). Bagi sempadan kiri, invarian menyatakan bahawa semua elemen sebelum left adalah lebih kecil daripada sasaran dan semua elemen bermula dari right dan seterusnya adalah lebih besar daripada atau sama dengannya. Jika titik tengah lebih kecil, jawapannya mestilah di sebelah kanan, jadi saya menetapkan left = middle + 1. Jika tidak, titik tengah mungkin merupakan jawapannya, jadi saya menetapkan right = middle. Apabila kedua-duanya bertemu, kedudukan tersebut ialah batas bawah. Batas atas hanya mengubah syaratnya: nilai yang kurang daripada atau sama dengan sasaran akan menggerakkan left.

Saya mengira batas bawah terlebih dahulu. Jika ia bersamaan dengan panjang tatasusunan atau tidak mengandungi sasaran, saya mengembalikan [-1, -1]. Jika tidak, titik akhir kanan ialah batas atas tolak satu. Input kosong, sasaran yang tiada, semua elemen duplikasi, dan padanan pada mana-mana titik akhir semuanya menggunakan logik yang sama.

Setiap lelaran membahagi dua selang tersebut, jadi dua carian masih O(log n) dan menggunakan ruang tambahan O(1). Saya akan mengesahkan kes sempadan tetap dan kemudian membandingkan tatasusunan tersusun rawak terhadap indexOf dan lastIndexOf. Saya tidak akan menggunakan target + 1, kerana ia mencipta sentinela di luar domain yang dinyatakan dan tidak boleh digeneralisasikan ke domain tersusun yang lain.”

Kesilapan Biasa

• Mencari mana-mana kejadian dan mengimbas ke luar → tatasusunan yang kesemuanya sama menjadi O(n) → lakukan carian perduaan untuk batas bawah dan batas atas secara berasingan.
• Mengembalikan nilai serta-merta apabila terdapat persamaan → padanan adalah sebarangan dan bukannya paling kiri atau paling kanan → kekalkan bahagian yang masih mungkin mengandungi sempadan.
• Memulakan right kepada panjang tatasusunan dan membaca nums[right] → titik akhir separuh terbuka tidak boleh dicapai → baca hanya middle dan tamatkan apabila kedua-dua titik akhir bertemu.
• Mengemas kini dengan left = middle → selang dua elemen mungkin tidak akan mengecut → gunakan middle + 1 apabila mengecualikan titik tengah.
• Mengembalikan titik sisipan untuk sasaran yang tiada → kedudukan sisipan yang sah bukan bermakna satu padanan → semak batas dan nums[first] !== target.
• Menggunakan target + 1 untuk sempadan kanan → ia bergantung pada pengganti luar domain atau yang tidak wujud → laksanakan kedudukan pertama yang lebih besar secara ketat daripada sasaran.
• Mencampurkan templat tertutup dan separuh terbuka → pemulaan, syarat gelung, dan kemas kini akan berkonflik → tulis semantik selang dan invarian sebelum menulis kod.
• Hanya menguji duplikasi di bahagian tengah → input kosong, titik akhir, dan sasaran yang tiada masih boleh gagal → tambah jadual sempadan dan ujian pembezaan rawak.
• Mendakwa susun-kemudian-cari masih O(log n) → operasi menyusun mendominasi jumlah kos → gunakan jaminan input tersusun atau kira semula kerumitan penuh.

Soalan Susulan dan Maklum Balas

Soalan susulan 1: Jika anda hanya perlu menguji sama ada sasaran itu wujud, adakah anda memerlukan dua carian?

Tidak. Jalankan satu carian batas bawah dan semak bahawa kedudukannya berada dalam julat dan sama dengan sasaran. Itu kekal O(log n). Jika pustaka standard menyediakan kontrak yang tepat ini, kod pengeluaran boleh menggunakannya secara langsung. Dua carian hanya diperlukan untuk mendapatkan kedua-dua hujung julat duplikasi.

Soalan susulan 2: Bagaimanakah anda mengembalikan bilangan kejadian sasaran?

Apabila sasaran wujud, bilangannya ialah upperBound - lowerBound. Apabila ia tiada, kedua-dua titik sisipan adalah sama, jadi perbezaannya juga sifar. Oleh itu, fungsi kiraan sahaja tidak perlu membaca sebarang elemen tatasusunan. Formula ini berfungsi kerana setiap elemen antara kedua-dua sempadan adalah sama dengan sasaran.

Soalan susulan 3: Apakah yang berubah jika tatasusunan disusun dalam tertib menurun?

Terbalikkan invarian dan perbandingannya. Batas bawah menurun boleh bermaksud nilai pertama yang kurang daripada atau sama dengan sasaran, dan sempadan yang satu lagi ialah nilai pertama yang kurang secara ketat daripadanya. Jangan hanya menterbalikkan tafsiran akhir sambil mengekalkan perbandingan asal. Tentukan predikat partisi terlebih dahulu, kemudian kemas kini selang daripada nilai kebenarannya.

Soalan susulan 4: Bagaimana jika elemen adalah objek dan carian menggunakan satu medan?

Cari pada kunci perbandingan yang tersusun, seperti createdAt. Jika pengekstrakan kunci mahal merentasi pertanyaan berulang, simpan tatasusunan kunci yang telah dipra-kira; dokumentasi Python juga mengesyorkan untuk melakukan caching atau pra-kiraan bagi kunci yang mahal. Urutan objek tidak boleh diubah suai semasa carian, jika tidak invarian tersusun tidak lagi kekal.

Soalan susulan 5: Bagaimana jika data berada dalam pangkalan data dengan indeks tersusun dan bukan dalam ingatan?

Jangan terjemahkan carian perduaan aplikasi kepada banyak pertanyaan jarak jauh. Biarkan indeks pangkalan data mencari julat tersebut, seperti kunci susunan stabil minimum dan maksimum yang sama dengan sasaran atau imbasan julat indeks. Satu perjalanan pergi balik rangkaian bagi setiap lelaran carian perduaan menukarkan perbandingan O(log n) kepada panggilan kependaman tinggi yang berulang dan mungkin melihat snapshot yang berbeza semasa penulisan serentak.

Soalan susulan 6: Bagaimanakah templat ini dilanjutkan kepada masalah “jawapan boleh laksana minimum”?

Takrifkan predikat monotonik, seperti setiap kapasiti di bawah x adalah tidak boleh laksana dan setiap kapasiti dari suatu titik seterusnya adalah boleh laksana. Kemudian gunakan batas bawah bagi predikat benar pertama ke atas ruang jawapan tersirat, menggantikan nums[middle] < target dengan !feasible(middle). Predikat mesti dibuktikan bertukar daripada palsu kepada benar hanya sekali; jika nilai kebenaran berselang-seli, carian perduaan tidak mempunyai asas ketepatan.