Find First and Last Position of Element in Sorted Array

Q: Apa kompleksitas waktu untuk menemukan posisi pertama dan terakhir?

Waktu O(log n) dan ruang O(1) , dengan dua pencarian biner. Keduanya tidak berhenti saat menemukan kecocokan, jadi biayanya tidak bergantung pada jumlah salinan target: sekitar 14 langkah per pencarian untuk 10^4 nilai.

Q: Apa itu batas bawah dalam pencarian biner?

Batas bawah suatu nilai adalah indeks pertama yang elemennya setidaknya sama dengan nilai tersebut, atau panjang list jika tidak ada. Di posisi itulah nilai akan disisipkan agar list tetap terurut. Batas atas adalah indeks pertama yang elemennya lebih besar dari nilai tersebut.

Q: Apakah satu fungsi binary search bisa menemukan indeks pertama dan terakhir?

Ya. Beri pencarian itu sebuah penanda: saat menemukan kecocokan, catat indeksnya lalu lanjutkan pencarian ke kiri untuk menemukan salinan pertama, atau ke kanan untuk menemukan salinan terakhir. Memanggil pencarian batas bawah pada target dan target + 1 juga bisa. Keduanya berjalan dalam O(log n) .

SedangBinary search

+10

Kamu mendapatkan sebuah list bilangan bulat nums yang diurutkan dalam urutan tidak menurun, sehingga suatu nilai dapat muncul berulang kali, dan sebuah bilangan bulat target. Kembalikan sebuah list berisi dua indeks, dihitung mulai dari 0: posisi pertama dan terakhir tempat target muncul. Jika target tidak ada dalam list, kembalikan [-1, -1]. Usahakan agar waktu yang dibutuhkan O(log n).

Fungsi

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

numsinteger-array: daftar bilangan bulat yang sudah diurutkan, yang nilainya mungkin berulang
targetinteger: nilai yang dicari
Mengembalikaninteger-array: indeks pertama dan terakhir dari target, atau [-1, -1] jika tidak ditemukan

Batasan

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
nums diurutkan dalam urutan yang tidak menurun.

Contoh

Input: nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
Output: [1, 3]
Penjelasan: Tiga salinan 5 berada di indeks 1, 2, dan 3, jadi perulangan dimulai dari 1 dan berakhir di 3. Indeks 0 berisi 3 dan indeks 4 berisi 8, jadi perulangan tidak dapat berlanjut lebih jauh.

Input: nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
Output: [-1, -1]
Penjelasan: 7 akan berada di antara 5 pada indeks 3 dan 8 pada indeks 4, dan keduanya bukan 7. List tersebut tidak berisi salinan, jadi jawabannya adalah [-1, -1].

Pertanyaan lanjutan

Jika list yang sama menerima ribuan kueri untuk target yang berbeda, bisakah satu kali pemrosesan sebelumnya membuat setiap kueri lebih cepat daripada O(log n)?

Petunjuk

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

0 dari 3 dibuka

Solusi

Pencarian biner biasa berhenti pada salinan target mana pun yang ditemukannya, dan salinan itu bisa berada di mana saja dalam rentetan tersebut. Cari batas bawah sebagai gantinya: indeks pertama yang nilainya setidaknya sama dengan angka tertentu. Batas bawah target dan target + 1 memberikan kedua ujung rentetan dalam O(log n).

Telusuri seluruh daftar

Intuisi

Telusuri list satu kali. Indeks pertama yang berisi target adalah awal dan indeks terakhir adalah akhir. Jika target tidak pernah muncul, keduanya tetap -1.

Cara ini bekerja pada list apa pun, terurut atau tidak, dan itulah kelemahannya: cara ini membaca semua n nilai. List dengan 10^4 nilai memerlukan 10.000 perbandingan, padahal sekitar 28 perbandingan saja sudah cukup.

Algoritma

Tetapkan first = last = -1.
Untuk setiap indeks i, jika nums[i] sama dengan target, tetapkan first = i jika first masih -1, lalu tetapkan last = i.
Kembalikan [first, last].

def searchRange(nums, target):
    first = last = -1
    for i, value in enumerate(nums):
        if value == target:
            if first == -1:
                first = i  # the first match fixes the start
            last = i  # every later match moves the end
    return [first, last]

Temukan satu salinan, lalu kembangkan

Intuisi

Gunakan binary search untuk mencari indeks yang berisi target. List sudah terurut, jadi semua salinannya berada dalam satu rentang berurutan di sekitar indeks itu: bergerak ke kiri dan kanan selama nilai tetangganya masih target.

Pencarian membutuhkan O(log n), lalu penelusuran membutuhkan satu langkah untuk setiap salinan, totalnya k. Jika sebagian besar list berisi target, misalnya 10^4 salinan, penelusuran akan membaca setiap nilai dan kamu kembali melakukan pemindaian linear.

Algoritma

Lakukan pencarian biner untuk menemukan indeks found dengan nums[found] == target.
Jika tidak ada, kembalikan [-1, -1].
Geser first ke kiri dari found selama nilai sebelumnya sama dengan target.
Geser last ke kanan dari found selama nilai setelahnya sama dengan target.
Kembalikan [first, last].

def searchRange(nums, target):
    # An ordinary binary search finds some copy of target, if there is one.
    lo, hi = 0, len(nums) - 1
    found = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            found = mid
            break
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    if found == -1:
        return [-1, -1]
    # The copies sit next to each other, so walk out to both ends of the run.
    first = last = found
    while first > 0 and nums[first - 1] == target:
        first -= 1
    while last < len(nums) - 1 and nums[last + 1] == target:
        last += 1
    return [first, last]

Dua pencarian biner batas bawah

Intuisi

Ajukan pertanyaan yang berbeda: apa indeks pertama yang nilainya setidaknya value? Indeks itu adalah batas bawah, atau n jika tidak ada nilai yang memenuhi syarat. Pertahankan rentang setengah terbuka [lo, hi) yang selalu mencakup indeks tersebut. Jika nums[mid] < value, berarti mid dan semua indeks sebelumnya terlalu kecil. Jika tidak, mid memenuhi syarat, tetapi indeks sebelumnya mungkin juga memenuhi syarat, jadi mid tetap berada dalam rentang sebagai hi yang baru. Perulangan tidak pernah berhenti lebih awal saat menemukan kecocokan.

Batas bawah target adalah tempat rentetannya dimulai. Nilainya berupa bilangan bulat, jadi nilai pertama yang lebih besar dari target berada pada batas bawah target + 1, dan rentetannya berakhir satu indeks sebelumnya. Pada contoh pertama, batas bawah 5 adalah 1 dan batas bawah 6 adalah 4, tempat 8 berada: rentetannya adalah [1, 3]. Kedua pencarian memerlukan sekitar 28 langkah untuk 10^4 nilai, berapa pun panjang rentetannya.

Algoritma

Tulis lowerBound(value): mulai dengan lo = 0, hi = n; selama lo < hi, jika nums[mid] < value, tetapkan lo = mid + 1, jika tidak, tetapkan hi = mid; kembalikan lo.
Tetapkan first = lowerBound(target).
Jika first == n atau nums[first] != target, kembalikan [-1, -1].
Tetapkan last = lowerBound(target + 1) - 1 dan kembalikan [first, last].

def lowerBound(nums, value):
    # The first index whose number is at least value, or len(nums) if none is.
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < value:
            lo = mid + 1  # nums[mid] and everything before it is too small
        else:
            hi = mid  # nums[mid] qualifies, but an earlier index might too
    return lo


def searchRange(nums, target):
    first = lowerBound(nums, target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    # The run of target ends right before the first number above target.
    last = lowerBound(nums, target + 1) - 1
    return [first, last]

Jebakan dan kasus tepi

Mengembalikan hasil segera setelah nums[mid] == target. Indeks itu bisa berada di mana saja dalam rentang yang sama: dalam [3, 5, 5, 5, 8], posisi tengah pertama adalah indeks 2, yang bukan salah satu ujung.
Menulis hi = mid - 1 dalam pencarian batas bawah saat nums[mid] ≥ value. Ini membuang mid, yang mungkin merupakan jawabannya.
Membaca nums[first] tanpa memeriksa first < n. Jika target lebih besar daripada semua nilai, seperti 13 dalam contoh, batas bawahnya adalah n, satu posisi setelah akhir.
Lupa menggeser posisi di Lua dan R. List keduanya dimulai dari 1, jadi kurangi 1 dari kedua posisi.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu untuk menemukan posisi pertama dan terakhir?

Waktu O(log n) dan ruang O(1), dengan dua pencarian biner. Keduanya tidak berhenti saat menemukan kecocokan, jadi biayanya tidak bergantung pada jumlah salinan target: sekitar 14 langkah per pencarian untuk 10^4 nilai.

Apa itu batas bawah dalam pencarian biner?

Batas bawah suatu nilai adalah indeks pertama yang elemennya setidaknya sama dengan nilai tersebut, atau panjang list jika tidak ada. Di posisi itulah nilai akan disisipkan agar list tetap terurut. Batas atas adalah indeks pertama yang elemennya lebih besar dari nilai tersebut.

Apakah satu fungsi binary search bisa menemukan indeks pertama dan terakhir?

Ya. Beri pencarian itu sebuah penanda: saat menemukan kecocokan, catat indeksnya lalu lanjutkan pencarian ke kiri untuk menemukan salinan pertama, atau ke kanan untuk menemukan salinan terakhir. Memanggil pencarian batas bawah pada target dan target + 1 juga bisa. Keduanya berjalan dalam O(log n).

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

Tes #1

Tes #2

Argumen

nums = [3, 5, 5, 5, 8, 9, 9, 12]
target = 5

Output yang diharapkan

[1, 3]

Find First and Last Position of Element in Sorted Array

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Telusuri seluruh daftar

Temukan satu salinan, lalu kembangkan

Dua pencarian biner batas bawah

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa