Binary Search

Q: Apa kompleksitas waktu dari pencarian biner?

Waktu O(log n) . Setiap perbandingan membagi dua rentang yang masih dapat berisi target, jadi list dengan 10^9 elemen memerlukan paling banyak 30 perbandingan. Versi iteratif menggunakan ruang ekstra O(1) .

Q: Apakah binary search sebaiknya menggunakan pendekatan iteratif atau rekursif?

Keduanya benar dan keduanya berjalan dalam waktu O(log n) . Versi rekursif menggunakan ruang stack O(log n) ; perulangan yang menggerakkan lo dan hi menggunakan O(1) . Pewawancara biasanya mengharapkan perulangan.

Q: Bagaimana cara menghindari overflow saat menghitung indeks tengah?

Tulis mid = lo + (hi - lo) / 2 , bukan (lo + hi) / 2 . Keduanya menghasilkan indeks yang sama, tetapi pada integer 32-bit, jumlah lo + hi mengalami overflow saat indeks melewati sekitar 1.07 × 10^9 . Python dan Ruby memiliki integer tanpa batas, jadi bentuk singkat ini aman digunakan di sana.

MudahBinary search

+10

Kamu mendapatkan list bilangan bulat nums yang diurutkan secara menaik, tanpa nilai yang berulang, dan sebuah bilangan bulat target. Kembalikan indeks target dalam nums, dihitung mulai dari 0, atau -1 jika tidak ada dalam list. Usahakan waktu O(log n), yang berarti kamu tidak bisa memeriksa setiap elemen.

Fungsi

search(nums: integer-array, target: integer) → integer

numsinteger-array: daftar bilangan bulat berbeda yang telah diurutkan
targetinteger: nilai yang dicari
Mengembalikaninteger: indeks target dalam nums, atau -1 jika tidak ditemukan

Batasan

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
nums diurutkan dalam urutan menaik ketat, jadi setiap nilai muncul satu kali.

Contoh

Input: nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
Output: 4
Penjelasan: nums[4] bernilai 9. Pencarian memeriksa indeks 3 (nilainya 4, terlalu kecil), lalu indeks 5 (nilainya 15, terlalu besar), lalu indeks 4, tempat nilai 9 ditemukan.

Input: nums = [1, 3, 5, 8, 13, 21]target = 10
Output: -1
Penjelasan: 10 berada di antara 8 dan 13, dan keduanya bukan 10, jadi 10 tidak ada dalam list. Rentang pencarian menyusut hingga lo melewati hi, lalu fungsi mengembalikan -1.

Pertanyaan lanjutan

Jika nums dapat memiliki nilai yang berulang, bagaimana kamu mengembalikan indeks pertama target, tetap dalam O(log n)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

list ini sudah diurutkan, jadi satu perbandingan dengan elemen tengah memberi tahu kamu bagian mana yang masih bisa memuat target. Dengan membuang setengah kandidat pada setiap langkah, list berisi 10^4 elemen hanya membutuhkan paling banyak 14 perbandingan, bukan 10.000.

Pindai dari kiri ke kanan

Intuisi

Bandingkan setiap elemen dengan target secara berurutan dan kembalikan kecocokan pertama, atau -1 setelah perulangan. Cara ini benar untuk daftar apa pun, baik terurut maupun tidak.

Cara ini tidak pernah memanfaatkan urutannya, jadi daftar dengan 10^4 elemen memerlukan hingga 10.000 perbandingan: O(n), bukan O(log n) seperti yang diminta oleh tugas.

Algoritma

Untuk setiap indeks i dari 0 hingga n-1, bandingkan nums[i] dengan target.
Jika keduanya sama, kembalikan i.
Setelah perulangan, kembalikan -1.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

Pencarian biner dengan dua indeks

Intuisi

Pertahankan dua indeks, lo dan hi, dengan satu jaminan: jika target ada di dalam list, indeksnya berada di antara keduanya, termasuk keduanya. Saat nums[mid] lebih kecil daripada target, semua elemen sampai mid juga lebih kecil karena list sudah diurutkan, jadi lo bisa bergerak melewati mid. Nilai nums[mid] yang lebih besar membuat hi bergerak ke posisi di bawah mid karena alasan yang sama. Jaminan itu tetap berlaku setelah setiap pergerakan.

Jika target tidak ada, rentangnya menyempit sampai lo melewati hi. Rentangnya pun kosong, jadi jaminan tersebut menyatakan bahwa target tidak ada di mana pun. Setiap langkah membagi rentang menjadi dua, jadi perulangan berjalan paling banyak sekitar log2(n) + 1 kali, dengan dua indeks sebagai memori tambahan.

Algoritma

Atur lo = 0 dan hi = n-1.
Selama lo ≤ hi, hitung mid = lo + (hi - lo) / 2.
Jika nums[mid] sama dengan target, kembalikan mid.
Jika nums[mid] < target, atur lo = mid + 1; jika tidak, atur hi = mid - 1.
Saat perulangan berakhir, kembalikan -1.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1  # nums[mid] and everything left of it is too small
        else:
            hi = mid - 1  # nums[mid] and everything right of it is too big
    return -1

Jebakan dan kasus tepi

Melakukan perulangan pada lo < hi saat hi dimulai dari indeks terakhir. Perulangan berhenti dengan satu kandidat yang belum diperiksa, jadi nums = [5] dengan target = 5 menghasilkan -1.
Mengubah nilai menjadi lo = mid atau hi = mid dengan rentang inklusif. Saat lo dan hi bersebelahan, mid sama dengan lo dan rentang tidak pernah menyusut: perulangan tanpa akhir.
Mengembalikan lo saat target tidak ditemukan. Setelah perulangan, lo adalah titik penyisipan, indeks yang valid, bukan -1.
Lupa menggeser indeks di Lua dan R. List-nya dimulai dari 1, jadi indeks yang kamu kembalikan adalah posisi dikurangi 1.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari pencarian biner?

Waktu O(log n). Setiap perbandingan membagi dua rentang yang masih dapat berisi target, jadi list dengan 10^9 elemen memerlukan paling banyak 30 perbandingan. Versi iteratif menggunakan ruang ekstra O(1).

Apakah binary search sebaiknya menggunakan pendekatan iteratif atau rekursif?

Keduanya benar dan keduanya berjalan dalam waktu O(log n). Versi rekursif menggunakan ruang stack O(log n); perulangan yang menggerakkan lo dan hi menggunakan O(1). Pewawancara biasanya mengharapkan perulangan.

Bagaimana cara menghindari overflow saat menghitung indeks tengah?

Tulis mid = lo + (hi - lo) / 2, bukan (lo + hi) / 2. Keduanya menghasilkan indeks yang sama, tetapi pada integer 32-bit, jumlah lo + hi mengalami overflow saat indeks melewati sekitar 1.07 × 10^9. Python dan Ruby memiliki integer tanpa batas, jadi bentuk singkat ini aman digunakan di sana.

def search(nums, target):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

nums = [-7, -2, 0, 4, 9, 15, 23]
target = 9

Output yang diharapkan