Wawancara Koding: Menemukan Posisi Pertama dan Terakhir dengan Binary Search

Masalah dan Konteks yang Berlaku

Diberikan sebuah array integer nums yang diurutkan secara tidak menurun dan sebuah integer target, kembalikan indeks pertama dan terakhir dari target. Kembalikan [-1, -1] jika tidak ditemukan. Array mungkin kosong dan mungkin berisi duplikat, serta fungsi tidak boleh memutasi array tersebut. Kompleksitas waktu yang diperlukan adalah O(log n) dengan ruang ekstra O(1).

Sebagai contoh, nums = [1, 2, 2, 2, 3] dan target = 2 mengembalikan [1, 3]; target = 4 mengembalikan [-1, -1]. Pemindaian linier (linear scan) dapat menghasilkan jawaban tersebut, tetapi skenario terburuknya yaitu O(n) melanggar persyaratan.

Pertanyaan ini cocok untuk sesi koding peran rekayasa perangkat lunak dan algoritma. Panduan wawancara SDE II Amazon saat ini mengharapkan kode yang benar secara sintaksis, terukur (scalable), tangguh (robust), dan teruji dengan baik, dan LeetCode mempertahankan masalah inti yang sama. Ujian sebenarnya bukanlah menghafal dua templat. Ujiannya adalah mendefinisikan batas pencarian dengan cukup tepat sehingga kondisi loop, pembaruan interval, dan nilai kembalian semuanya mengikuti satu invarian.

Apa yang Dinilai oleh Pewawancara

Sinyal pertama adalah apakah kandidat menyadari bahwa menemukan kemunculan sembarang saja tidak cukup. Pencarian biner biasa yang langsung mengembalikan nilai saat kondisi sama dengan terpenuhi tidak menjamin kemunculan paling kiri atau paling kanan. Menemukan satu kemunculan lalu memindai ke arah luar tetap akan terdegradasi menjadi O(n) ketika setiap elemen bernilai sama dengan target.

Sinyal kedua adalah semantik batas. Dekomposisi yang bersih melakukan pencarian untuk dua titik penyisipan (insertion points):

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

Modul resmi Python bisect_left dan bisect_right menggunakan definisi partisi ini. Setelah kedua titik tersebut benar, target yang ada menempati [lowerBound, upperBound - 1].

Sinyal ketiga adalah invarian loop. Dengan interval setengah terbuka [left, right), array kosong secara alami dimulai sebagai [0, 0), dan terminasinya adalah left === right. Mencampur aturan interval tertutup dengan inisialisasi setengah terbuka, seperti mengatur right ke nums.length dan kemudian membaca nums[right], menyebabkan akses di luar batas (out-of-bounds) atau loop tak terbatas.

Akhirnya, pewawancara mencari verifikasi. Jawaban yang kuat mencakup array kosong, satu elemen, semua elemen duplikat, target di bawah nilai minimum, target di atas nilai maksimum, target di kedua ujung, dan target yang tidak ada. Jawaban tersebut juga menjelaskan mengapa target + 1 bukanlah teknik batas atas yang umum: teknik ini bergantung pada suksesor numerik diskret, menciptakan nilai di luar domain pada integer aman terbesar, dan tidak dapat diterapkan pada string atau pembanding kustom.

Pertanyaan Klarifikasi Sebelum Menjawab

• Apakah array sudah terurut? Perintah ini menjamin urutan tidak menurun. Mengurutkan input yang belum terurut sambil

mempertahankan indeks asli akan mengubah model data dan menghilangkan batasan total O(log n).

• Apakah kita mengembalikan indeks asli atau indeks yang terurut? Keduanya sama di sini karena input sudah terurut.
• Apa yang merepresentasikan ketiadaan elemen? Perintah ini memerlukan [-1, -1]; titik penyisipan tidak otomatis merupakan kecocokan.
• Apakah nilai duplikat diperbolehkan? Ya. Duplikat adalah alasan mengapa pencarian batas diperlukan.
• Bolehkah array kosong? Ya. Implementasi setengah terbuka menanganinya tanpa membaca kedua titik akhir.
• Berapa domain numeriknya? Nilainya adalah integer aman JavaScript. Solusi ini tidak menghitung target + 1, sehingga

tidak membuat sentinel di luar domain hanya untuk menemukan batas.

• Haruskah binary search diimplementasikan sendiri? Ya untuk latihan wawancara ini. Dalam produksi, lebih disukai fungsi

pustaka standar ketika kontrak perilakunya cocok persis.

• Bolehkah input dimutasi? Tidak, dan tidak ada pencarian batas yang perlu memutasinya.

Kerangka Jawaban 30 Detik

“Saya akan menjalankan dua pencarian batas alih-alih menemukan satu kemunculan lalu memindai. lowerBound mencari pada interval setengah terbuka [left, right) untuk nilai pertama yang lebih besar dari atau sama dengan target; upperBound mencari nilai pertama yang secara ketat lebih besar dari target. Setiap iterasi menggunakan middle = left + floor((right - left) / 2). Jika titik tengah masih berada di sisi kiri target, atur left = middle + 1; jika tidak, pertahankan titik tengah dengan right = middle. Pertama-tama saya memeriksa apakah batas bawah berada di luar rentang atau tidak sama dengan target. Jika ada, jawabannya adalah [lower, upper - 1]. Dua pencarian tetap menghasilkan O(log n) dengan ruang ekstra O(1).”

Penjelasan Mendalam Langkah demi Langkah

Langkah 1: Tulis ulang “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]

Definisi ini lebih mudah diverifikasi daripada “terus mencari ke kiri” dan “terus mencari ke kanan.” Titik penyisipan tetap bermakna saat target tidak ada. Untuk target = 4, keduanya sama dengan panjang array 5, tetapi itu tidak berarti targetnya ada. Algoritma harus memeriksa secara terpisah nums[lower] === target.

Langkah 2: Tetapkan invarian interval setengah terbuka.

Pada awal setiap iterasi lowerBound:

1. Setiap indeks di bawah left berisi nilai yang secara ketat lebih kecil dari target.
2. Setiap indeks pada atau di atas right berisi nilai yang lebih besar dari atau sama dengan target.
3. Interval kandidat yang belum terselesaikan adalah [left, right).

Awalnya, left = 0 dan right = nums.length; kedua wilayah luar kosong, sehingga invarian tetap berlaku. Jika nums[middle] < target, titik tengah dan semua elemen di sebelah kirinya tidak mungkin menjadi jawaban, jadi atur left = middle + 1. Jika tidak, titik tengah mungkin merupakan posisi valid pertama dan harus dipertahankan, jadi atur right = middle.

Setiap iterasi secara ketat memperpendek interval. Ketika left === right, tidak ada elemen yang belum terselesaikan yang tersisa. Semua elemen di sebelah kiri lebih kecil dan semua elemen di sebelah kanan lebih besar dari atau sama dengan target, sehingga posisi ini adalah batas bawah.

upperBound menggunakan struktur yang sama dengan partisi yang berbeda:

1. Setiap indeks di bawah left berisi nilai yang lebih kecil dari atau sama dengan target.
2. Setiap indeks pada atau di atas right berisi nilai yang secara ketat lebih besar dari target.

Oleh karena itu, ia memindahkan left ketika nums[middle] <= target dan sebaliknya memindahkan right.

Langkah 3: Implementasikan kedua fungsi batas.

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 perbedaan adalah pada perbandingannya. Dua fungsi yang diberi nama jelas lebih mudah dijelaskan dalam wawancara daripada satu fungsi dengan switch Boolean yang tidak transparan, dan keduanya menghindari pembuatan abstraksi generik yang rumit hanya untuk satu penggunaan.

Titik tengahnya adalah left + floor((right - left) / 2), sehingga tidak menjumlahkan dua indeks besar terlebih dahulu. Batasan array runtime JavaScript membuat overflow indeks tidak mungkin terjadi dalam konteks ini, tetapi ekspresi tersebut berpindah dengan aman ke bahasa bertipe integer dengan lebar tetap.

Langkah 4: Gabungkan hasil dan verifikasi kecocokan sebenarnya.

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 pemeriksaan sangat penting. Uji first === nums.length sebelum membaca nums[first], sehingga posisi setelah array tidak diperlakukan sebagai elemen. Setelah first diketahui cocok, batas atas setidaknya bernilai first + 1, dan menguranginya dengan satu akan menghasilkan kemunculan terakhir.

Jangan mengganti batas atas dengan lowerBound(nums, target + 1) - 1. Di bawah batasan safe-integer pada soal ini, pendekatan tersebut mungkin masih mengembalikan batas yang tepat, tetapi menambahkan satu ke Number.MAX_SAFE_INTEGER akan keluar dari domain tempat aritmatika integer yang presisi dijamin. Jika input meluas ke sembarang Number JavaScript, integer yang berdekatan juga dapat runtuh akibat presisi floating-point. String, nilai BigInt, dan pembanding kustom tidak memiliki “nilai berikutnya” yang universal. Mencari langsung nilai pertama yang secara ketat lebih besar dari target mengekspresikan kontrak secara lengkap.

Langkah 5: Buktikan kompleksitasnya.

Setiap loop mengurangi interval kandidat dengan panjang k menjadi paling banyak sekitar k / 2, sehingga setiap fungsi batas melakukan O(log n) perbandingan. Dua pencarian tetap berada dalam O(log n). Algoritma ini hanya menyimpan sejumlah konstan indeks, menggunakan ruang ekstra O(1), dan tidak memutasi array.

Menemukan kemunculan sembarang lalu memindai ke luar akan mengunjungi semua n elemen untuk [2, 2, ..., 2], menghasilkan skenario terburuk O(n). Tabel hash yang telah dihitung sebelumnya dapat membuat pencarian berulang menjadi cepat, tetapi pembuatannya membutuhkan waktu dan ruang O(n). Ini hanya berguna untuk banyak kueri pada input statis yang sama dan mengabaikan keuntungan urutan terurut yang telah diberikan.

Langkah 6: Validasi dengan kasus batas dan uji diferensial teracak.

Minimal, cakup kasus-kasus berikut:

Kemudian buat array terurut dengan duplikat dan bandingkan hasilnya dengan baseline linier indexOf dan lastIndexOf. Pendekatan linier memang tidak memenuhi target kompleksitas, tetapi merupakan test oracle yang sangat baik. Kasus tetap memeriksa batas yang diketahui, sementara uji diferensial teracak menyingkap kesalahan yang terkait dengan jumlah duplikat atau titik akhir tertentu.

Contoh Jawaban Berkualitas Tinggi

“Array sudah terurut dan persyaratannya adalah O(log n), jadi saya tidak akan mencari satu target lalu memindai ke luar; array yang semua elemennya duplikat akan menjadi linier. Saya mendefinisikan jawabannya dengan dua titik penyisipan: nilai pertama yang lebih besar dari atau sama dengan target, dan nilai pertama yang secara ketat lebih besar dari target.

Kedua pencarian menggunakan interval setengah terbuka [left, right). Untuk batas kiri, invarian menyatakan bahwa semua elemen sebelum left lebih kecil dari target dan semua elemen mulai dari right dan seterusnya lebih besar dari atau sama dengan target. Jika titik tengah lebih kecil, jawabannya pasti ada di sebelah kanan, jadi saya mengatur left = middle + 1. Jika tidak, titik tengah mungkin adalah jawabannya, jadi saya mengatur right = middle. Ketika keduanya bertemu, posisi tersebut adalah batas bawah. Batas atas hanya mengubah kondisinya: nilai yang kurang dari atau sama dengan target akan memindahkan left.

Saya menghitung batas bawah terlebih dahulu. Jika nilainya sama dengan panjang array atau tidak berisi target, saya mengembalikan [-1, -1]. Jika tidak, titik akhir kanan adalah batas atas dikurangi satu. Input kosong, target yang hilang, semua elemen duplikat, dan kecocokan di salah satu titik akhir semuanya menggunakan logika yang sama.

Setiap iterasi membagi dua interval, sehingga dua pencarian tetap berjalan dalam O(log n) dan menggunakan ruang ekstra O(1). Saya akan memverifikasi kasus batas tetap dan kemudian membandingkan array terurut acak terhadap indexOf dan lastIndexOf. Saya tidak akan menggunakan target + 1, karena teknik tersebut membuat sentinel di luar domain yang ditentukan dan tidak dapat digeneralisasi ke domain terurut lainnya.”

Kesalahan Umum

• Menemukan kemunculan sembarang lalu memindai ke luar → array yang semua elemennya sama menjadi O(n) → lakukan binary search untuk batas bawah dan batas atas secara terpisah.
• Langsung mengembalikan nilai saat kondisi sama terpenuhi → hasil yang didapat bersifat sembarang alih-alih paling kiri atau paling kanan → pertahankan bagian yang masih mungkin memuat batas.
• Menginisialisasi right ke panjang array dan membaca nums[right] → titik akhir setengah terbuka tidak dapat diakses → baca hanya middle dan hentikan saat kedua titik akhir bertemu.
• Memperbarui dengan left = middle → interval dua elemen mungkin tidak akan pernah menyusut → gunakan middle + 1 saat mengecualikan titik tengah.
• Mengembalikan titik penyisipan untuk target yang tidak ada → posisi penyisipan yang valid bukanlah sebuah kecocokan → periksa batasan dan nums[first] !== target.
• Menggunakan target + 1 untuk batas kanan → hal ini bergantung pada suksesor di luar domain atau yang tidak ada → implementasikan posisi pertama yang secara ketat lebih besar dari target.
• Mencampur templat tertutup dan setengah terbuka → inisialisasi, kondisi loop, dan pembaruan akan saling bertentangan → tulis semantik interval dan invarian sebelum menulis kode.
• Hanya menguji duplikat di bagian tengah → input kosong, titik akhir, dan elemen yang tidak ditemukan masih bisa gagal → tambahkan tabel kasus batas dan uji diferensial teracak.
• Mengklaim urutkan-lalu-cari tetap O(log n) → pengurutan mendominasi total biaya komputasi → manfaatkan jaminan input terurut atau hitung ulang kompleksitas totalnya.

Pertanyaan Lanjutan dan Tanggapannya

Pertanyaan Lanjutan 1: Jika Anda hanya perlu menguji apakah target ada, apakah Anda memerlukan dua pencarian?

Tidak. Jalankan satu pencarian batas bawah dan periksa apakah posisinya berada dalam rentang serta bernilai sama dengan target. Itu tetap bernilai O(log n). Jika pustaka standar menyediakan kontrak yang persis seperti ini, kode produksi dapat menggunakannya secara langsung. Dua pencarian hanya diperlukan untuk mendapatkan kedua ujung rentang duplikat.

Pertanyaan Lanjutan 2: Bagaimana cara mengembalikan jumlah kemunculan target?

Ketika target ada, jumlahnya adalah upperBound - lowerBound. Ketika target tidak ada, kedua titik penyisipan bernilai sama, sehingga perbedaannya juga nol. Oleh karena itu, fungsi yang hanya menghitung kemunculan bahkan tidak perlu membaca elemen array. Rumus ini berfungsi karena setiap elemen di antara kedua batas tersebut bernilai sama dengan target.

Pertanyaan Lanjutan 3: Apa yang berubah jika array diurutkan secara menurun (descending)?

Balikkan invarian dan perbandingannya. Batas bawah menurun dapat berarti nilai pertama yang kurang dari atau sama dengan target, dan batas lainnya adalah nilai pertama yang secara ketat kurang dari target. Jangan hanya membalikkan interpretasi akhir sambil mempertahankan perbandingan aslinya. Tentukan predikat partisi terlebih dahulu, lalu perbarui interval berdasarkan nilai kebenarannya.

Pertanyaan Lanjutan 4: Bagaimana jika elemen-elemen berupa objek dan pencarian menggunakan satu field?

Cari pada kunci perbandingan yang terurut, seperti createdAt. Jika ekstraksi kunci memakan biaya komputasi tinggi pada kueri berulang, simpan array kunci yang telah dihitung sebelumnya; dokumentasi Python juga menyarankan untuk melakukan caching atau menghitung kunci yang mahal di awal. Urutan objek tidak boleh dimutasi selama pencarian, atau invarian terurut tidak akan berlaku lagi.

Pertanyaan Lanjutan 5: Bagaimana jika data berada di dalam database dengan indeks terurut dan bukan di dalam memori?

Jangan menerjemahkan binary search aplikasi menjadi banyak kueri jarak jauh (remote queries). Biarkan indeks database mencari rentang tersebut, seperti kunci pengurutan stabil minimum dan maksimum yang sama dengan target atau pemindaian rentang indeks (index range scan). Satu round trip jaringan per iterasi binary search akan mengubah perbandingan O(log n) menjadi panggilan berlatensi tinggi yang berulang dan dapat melihat snapshot yang berbeda selama penulisan bersamaan (concurrent writes).

Pertanyaan Lanjutan 6: Bagaimana templat ini diperluas ke masalah “jawaban layak minimum” (minimum feasible answer)?

Definisikan predikat monotonik, seperti setiap kapasitas di bawah x tidak layak dan setiap kapasitas dari titik tertentu ke atas adalah layak. Kemudian terapkan batas bawah untuk predikat bernilai true pertama di atas ruang jawaban implisit, menggantikan nums[middle] < target dengan !feasible(middle). Predikat tersebut harus terbukti bertransisi dari false ke true hanya satu kali; jika nilai kebenarannya bergantian, binary search tidak memiliki dasar kebenaran matematis.