Pencarian Biner dan Pengurutan

Bagaimana pencarian biner menemukan sebuah nilai?

Pencarian biner melihat elemen tengah daftar terurut: jika itu target, pencarian selesai; jika target lebih besar, semua di kiri gugur; jika lebih kecil, semua di kanan gugur. Ulangi pada separuh yang tersisa. Ia adalah permainan "aku memikirkan bilangan dari 1 sampai 1000" yang dimainkan dengan baik: tebak 500, dengar "lebih besar", tebak 750, dan seterusnya. Tak seorang pun memerlukan lebih dari 10 tebakan.

Algoritmanya. Simpan dua indeks, lo dan hi, dengan janji (invarian) bahwa jika target ada dalam daftar, indeksnya berada di antara lo dan hi, ujung-ujungnya termasuk. Mulai dengan lo = 0 dan hi = n - 1. Selama lo <= hi: lihat mid, indeks tengah; jika a[mid] sama dengan target, kembalikan mid; jika lebih kecil, setel lo = mid + 1; jika tidak, setel hi = mid - 1. Jika selangnya menjadi kosong, target tidak ada.

Mengapa benar. Invarian benar di awal. Melihat mid menggugurkan mid sendiri dan satu sisi utuh: jika a[mid]<x, daftarnya terurut, sehingga setiap elemen di mid atau sebelumnya lebih kecil daripada x dan target, bila ada, berada di kanan. Jadi invarian tetap berlaku setelah setiap langkah. Daftarnya harus terurut, dan harus memungkinkan lompatan ke tengah dalam satu langkah (larik, bukan linked list); jika tidak, argumen dan kecepatannya hilang.

Mengapa cepat. Selang selebar w menjadi selang selebar paling banyak \lfloor w/2\rfloor. Dimulai dari n, setelah k kali melihat lebarnya paling banyak \lfloor n/2^k\rfloor, yaitu 0 begitu 2^k>n. Jadi banyaknya melihat paling banyak \lfloor\log_2n\rfloor+1. Itu 10 untuk 1000 elemen, 20 untuk sejuta, 30 untuk semiliar, dan 33 untuk delapan miliar: setiap penggandaan daftar hanya menambah satu kali melihat. Pemindaian linear atas daftar yang sama dapat memerlukan n kali (Notasi Big-O menjelaskan kasus-kasusnya).

Ketik daftar dan target di bawah lalu telusuri pencariannya. Sel oranye adalah yang sedang dilihat, sel pudar sudah gugur, dan sel hijau adalah jawabannya.

Bagaimana menemukan kecocokan pertama dan menghindari galat selisih satu?

Pakai satu templat untuk setiap pertanyaan tentang posisi: simpan selang indeks setengah terbuka lo <= i < hi yang di dalamnya semua yang sebelum lo diketahui terlalu kecil dan semua dari hi ke belakang diketahui cukup besar. Dengan nilai kembar, "cari x" tidak punya jawaban tunggal, tetapi "indeks pertama dengan a[i]\ge x" selalu punya. Pada daftar [1,3,3,5,7,7,7,9,12]:

Batas atas dikurangi batas bawah adalah banyaknya salinan x: 7-4=3. Bila x tidak ada, batas bawah adalah titik sisip, indeks tempat x akan ditaruh agar daftar tetap terurut, dan ia bisa bernilai n (melewati ujung).

Templatnya. Mulai dengan lo = 0, hi = n (satu setelah indeks terakhir). Selama lo < hi: ambil mid = lo + (hi - lo) // 2; jika a[mid] < x maka lo = mid + 1 (batas bawah ada di kanan mid), jika tidak hi = mid (mid mungkin jawabannya, jadi simpan). Ketika perulangan berakhir, lo == hi adalah jawabannya. Untuk batas atas, ubah ujinya menjadi a[mid] <= x. Invarian adalah seluruh buktinya: semua sebelum lo bernilai <x, semua dari hi bernilai \ge x, dan setiap langkah memperkecil hi - lo sedikitnya satu, sehingga perulangan berakhir.

Dari mana galat selisih satu berasal. Dari mencampur dua konvensi: selang tertutup lo <= i <= hi berpasangan dengan hi = n - 1, while lo <= hi, dan hi = mid - 1; selang setengah terbuka lo <= i < hi berpasangan dengan hi = n, while lo < hi, dan hi = mid. Menulis hi = mid pada selang tertutup dapat berputar tanpa henti pada dua elemen, dan hi = mid - 1 pada yang setengah terbuka dapat melewatkan jawabannya. Pilih satu dan tulis invariannya sebagai komentar. Jon Bentley mendapati bahwa kebanyakan pemrogram profesional yang ia uji tidak dapat menulis pencarian biner yang benar, dan Donald Knuth mengamati bahwa pencarian biner pertama diterbitkan pada 1946 tetapi yang benar untuk setiap panjang baru muncul pada 1962.

Galat luapan. Titik tengah adalah rata-rata lo dan hi, dan rumus yang paling mudah, (lo + hi) / 2, menjumlahkan keduanya lebih dulu. Dalam bahasa dengan bilangan bulat 32-bit, jumlah dua indeks yang sah dapat lebih besar daripada 2 147 483 647 dan berputar menjadi bilangan negatif (lihat komplemen dua), seperti pada lo = 1 500 000 000 dan hi = 2 000 000 000. Pada 2006 Joshua Bloch melaporkan bahwa ini sudah bertahun-tahun ada dalam pencarian biner pustaka Java. Bentuk yang aman adalah lo + (hi - lo) / 2: selisihnya tidak pernah lebih besar daripada hi.

Bagaimana mencari jawaban, bukan nilai, dengan pencarian biner?

Pencarian biner sama sekali tidak memerlukan daftar, hanya pertanyaan ya atau tidak yang salah untuk bilangan kecil dan benar untuk bilangan besar: jawabannya adalah tempat ia berganti. Pertanyaan itu dapat diajukan tentang bilangan apa pun, daftarnya tidak perlu ada, dan perulangan yang sama menemukan pergantiannya dalam sekitar \log_2 banyaknya calon.

• Akar kuadrat bulat. r terbesar dengan r^2\le N: ujinya "m^2\le N" benar untuk m sampai \lfloor√ N\rfloor dan salah sesudahnya. Untuk N=123 456 789 pencarian antara 0 dan N memerlukan 27 pengujian untuk menemukan 11 111 (karena 11 111^2=123 454 321 dan 11 112^2=123 476 544); menghitung naik dari nol memerlukan 11 111. N mana pun sampai 10^12 memerlukan paling banyak 40 pengujian.
• Mencari komit yang rusak. git bisect menanyakan apakah suatu versi baik atau rusak; riwayatnya beralih dari baik ke rusak sekali saja, sehingga di antara 1000 komit ia menemukan yang pertama rusak dalam 10 pengujian.
• Pertanyaan kapasitas. "Berapa ukuran truk terkecil yang mengantar semuanya dalam D hari?" Yang lebih besar selalu berhasil bila yang lebih kecil berhasil, jadi lakukan pencarian biner pada ukurannya, dan cukup tulis perulangan pengeceknya.
• Akar sebuah fungsi. Jika f kontinu dan f(a) serta f(b) berlawanan tanda, ada akar di antaranya. Lihat titik tengah, dan simpan separuh yang ujung-ujungnya masih berlawanan tanda. Inilah bisection: setiap langkah membagi dua kurungan dan menambah \log_102≈0,30 angka desimal, sehingga 50 pembagian dua pada [1,2] menjepit √2 sampai 2^-50≈8,9×10^-16, sekitar lima belas angka.

Bisection melawan metode Newton. Metode Newton menggandakan banyaknya angka benar pada setiap langkah, jauh lebih cepat, tetapi ia memerlukan turunan dan titik awal yang baik dan dapat keluar dari selang atau berputar (lihat kapan ia gagal). Bisection hanya memperoleh satu angka biner per langkah tetapi tidak dapat gagal begitu tandanya berganti. Banyak penyelesai memakai keduanya: bisection agar aman, metode Newton agar cepat.

Kehati-hatian pada bilangan titik mengambang. Dengan bilangan real jangan berulang "sampai hi - lo < 1e-18": di sekitar 1 jarak antardouble adalah 2,2×10^-16 (lihat jarak antarbilangan titik mengambang), sehingga hi - lo tidak pernah lebih kecil daripada itu dan perulangan tidak pernah berakhir. Ulangi sebanyak tetap (60 cukup untuk kurungan double mana pun) atau berhenti ketika mid sama dengan lo atau hi.

Cobalah keduanya di bawah: sebuah rumus dan selang, atau sebuah bilangan bulat.

Bagaimana selection, insertion, dan bubble sort bekerja?

Selection, insertion, dan bubble sort adalah tiga pengurutan sederhana: masing-masing memerlukan sekitar (n^2)/(2) langkah, ketiganya pendek untuk ditulis, dan merupakan pilihan yang tepat hanya untuk daftar pendek atau hampir terurut.

• Selection sort. Cari yang terkecil dari bagian yang belum terurut lalu tukar ke depan; ulangi. Ia membuat tepat (n(n-1))/(2) perbandingan apa pun masukannya, tetapi paling banyak n-1 pertukaran: yang dipakai bila memindahkan satu elemen sangat mahal.
• Insertion sort. Ambil bilangan berikutnya dan geser ke kiri melewati setiap tetangga yang lebih besar, seperti yang kamu lakukan dengan kartu di tangan. Pada daftar terurut tiap bilangan dibandingkan sekali (n-1 perbandingan seluruhnya); pada daftar terbalik setiap bilangan bergeser sampai ujung.
• Bubble sort. Berjalan menyusuri daftar sambil menukar tetangga yang salah urutan; bilangan terbesar terbawa ke ujung pada putaran pertama, yang terbesar berikutnya pada putaran kedua, dan seterusnya. Dengan penanda yang berhenti setelah putaran tanpa pertukaran, daftar terurut hanya memerlukan satu putaran.

Inversi menjelaskan biayanya. Inversi adalah pasangan posisi i<j dengan a[i]>a[j]. Daftar [5,2,4,6,1,3] memiliki 9: (5,2), (5,4), (5,1), (5,3), (2,1), (4,1), (4,3), (6,1), dan (6,3). Daftar terurut memiliki 0 dan daftar terbalik memiliki (n(n-1))/(2), semua pasangan; daftar acak memiliki sekitar setengahnya, (n(n-1))/(4). Menukar dua tetangga yang salah urutan menghilangkan tepat satu inversi, demikian pula satu geseran insertion sort. Jadi bubble sort membuat pertukaran sebanyak inversi, dan insertion sort geseran sebanyak inversi, tepat, dan metode apa pun yang hanya memindahkan tetangga memerlukan sekitar (n^2)/(4) langkah pada daftar acak. Agar lebih cepat, pengurutan harus memindahkan elemen melintasi jarak jauh: itulah yang dilakukan merge sort dan quicksort.

Pilih algoritma dan masukan di bawah lalu putar batangnya. Batang emas sedang dibandingkan, yang merah sedang pindah, dan yang hijau sudah di tempat akhirnya.

Bagaimana merge sort mengurutkan dalam n log n langkah?

Merge sort membagi daftar menjadi dua, mengurutkan setiap separuh dengan cara yang sama, lalu menggabungkan kedua separuh terurut itu menjadi satu. Penggabungan adalah bagian yang mudah: dua daftar terurut memiliki elemen terkecilnya di depan, jadi bandingkan kedua depan itu, pindahkan yang lebih kecil ke keluaran, dan ulangi. Menggabungkan daftar dengan panjang total n memerlukan paling banyak n-1 perbandingan dan tepat n penulisan.

Rekursinya membagi dua daftar sampai tersisa elemen tunggal (yang sudah terurut), sehingga ada \lceil\log_2n\rceil tingkat, dan setiap tingkat menggabungkan semua n elemen sekali. Itu n penulisan per tingkat dan totalnya sekitar n\log_2n. Rekurensinya T(n)=2T(n/2)+n, diselesaikan pada bagian tentang rekurensi. Dalam angka eksak:

• penulisan: 8 bilangan memerlukan 24=8·3, dan 1000 memerlukan 9976;
• perbandingan, kasus terburuk: n\lceil\log_2n\rceil-2^\lceil\log_2n\rceil+1, yaitu 17 untuk 8 bilangan dan 8977 untuk 1000;
• perbandingan, sudah terurut: sekitar setengahnya, karena satu daftar habis lebih dulu: 12 untuk 8 bilangan.

Sifat-sifatnya. Merge sort memerlukan memori tambahan O(n) untuk keluaran gabungan, ia stabil (jika dua elemen sama, ambil yang dari separuh kiri lebih dulu, yaitu <= dalam kode di bawah), dan biayanya hampir tidak bergantung pada masukan. Ia pilihan yang wajar untuk linked list dan untuk data di cakram atau pita, yang dibaca berurutan; ia pengurutan komputer pertama, diprogram oleh John von Neumann pada 1945.

Bagaimana quicksort bekerja, dan kapan ia lambat?

Quicksort memilih sebuah pivot, memindahkan elemen yang lebih kecil ke depannya dan yang lain ke belakangnya, lalu mengurutkan kedua sisi dengan cara yang sama. Setelah partisi, pivot sudah berada di tempat akhirnya. Partisi Nico Lomuto, yang dipakai dalam kode di bawah, mengambil elemen terakhir sebagai pivot dan menyapu dari kiri ke kanan sambil menjaga batas p: setiap elemen yang lebih kecil daripada pivot ditukar ke batas, yang lalu maju satu langkah. Partisi asli Tony Hoare memakai dua penunjuk yang bergerak saling mendekat dan melakukan lebih sedikit pertukaran.

Biayanya. Partisi m elemen membuat m-1 perbandingan. Jika pivot membagi rentang kira-kira dua sama besar setiap kali, ada sekitar \log_2n tingkat dengan sekitar n perbandingan masing-masing. Jika pivot selalu elemen terkecil atau terbesar, kedua sisi berukuran 0 dan m-1 dan totalnya (n-1)+(n-2)+…+1=(n(n-1))/(2), kuadratik. Dengan elemen terakhir sebagai pivot, hal ini terjadi pada daftar yang sudah terurut atau terbalik, persis masukan yang sering diberikan orang. Pada daftar acak rata-ratanya 2(n+1)H_n-4n≈2n\ln n≈1,39 n\log_2n, dengan H_n=1+\frac12+…+\frac1n. Untuk 1000 elemen itu sekitar 10 986 perbandingan (dibandingkan paling banyak 8977 untuk merge sort), dan peluang jalannya sangat buruk amat kecil.

Yang dilakukan implementasi sungguhan. - Memilih pivot dengan baik: elemen acak, atau median dari yang pertama, tengah, dan terakhir. - Menangani kunci yang sama: partisi tiga arah (lebih kecil, sama, lebih besar) menjaga daftar dengan sedikit nilai berbeda tidak melambat. - Membatasi kerusakan: introsort (David Musser, 1997) beralih ke heapsort jika rekursi terlalu dalam, sehingga kasus terburuknya O(n\log n); ia ada di balik std::sort C++. Merekursi sisi yang lebih kecil lebih dulu menjaga tumpukan tetap O(\log n). - Quicksort tidak stabil, dan ia mengurutkan di tempat, tanpa larik tambahan. Sapuan yang ramah cache membuatnya lebih cepat daripada merge sort pada larik dalam praktik, meskipun perbandingannya lebih banyak.

Balapan pengurutan di bawah menjalankan keenam algoritma pada masukan yang sama dan menghitung perbandingan serta perpindahan.

Algoritma pengurutan mana yang sebaiknya dipakai?

Dalam praktik, panggil fungsi pengurutan bahasamu: ia hibrida yang sudah disetel, dan hampir selalu lebih cepat dan lebih benar daripada apa pun yang akan kamu tulis. Tetapi ketahui apa yang dijanjikannya.

Tiga sifat menentukan pilihan. Stabil: kunci yang sama mempertahankan urutan awalnya, yang memungkinkan mengurutkan menurut beberapa kunci berturut-turut (urutkan menurut nama, lalu secara stabil menurut kota, dan setiap kota tetap terurut menurut nama). Di tempat: hanya memerlukan memori tambahan O(1) atau O(\log n). Adaptif: lebih cepat pada masukan yang hampir terurut, seperti insertion sort. Heapsort membangun max-heap di dalam larik, lalu berulang kali menukar yang terbesar ke ujung dan memperbaiki heap: di tempat dan O(n\log n) pada kasus terburuk, tetapi tidak stabil dan tidak ramah cache.

Sebuah batas dan cara mengelilinginya. Pengurutan apa pun yang hanya membandingkan elemen memerlukan sedikitnya \log_2(n!)≈ n\log_2n-1,44n perbandingan, karena n! urutan yang mungkin harus dibedakan dengan jawaban ya atau tidak (gagasan batas bawah dalam bagian tentang kasus). Untuk 1000 elemen itu 8530 perbandingan, dan kasus terburuk merge sort, 8977, hanya sekitar 5 persen di atasnya. Pengurutan yang tidak membandingkan bisa lebih cepat: counting sort menghitung berapa kali tiap nilai muncul (O(n+k) untuk nilai di bawah k), dan radix sort mengurutkan angka demi angka dengan pengurutan stabil, begitulah cara pengurut kartu berlubang bekerja.

Yang dilakukan pustaka. - Python: sorted(a) mengembalikan daftar baru dan a.sort() mengurutkan di tempat dan mengembalikan None. Keduanya memakai Timsort (Tim Peters, 2002): ia menemukan bagian yang sudah berurutan, memperpanjang bagian pendek dengan insertion sort dan menggabungkan bagian-bagiannya, sehingga stabil, O(n\log n), dan O(n) pada masukan terurut. - JavaScript: array.sort() stabil sejak 2019, tetapi tanpa pembanding ia membandingkan elemen sebagai teks, sehingga [10, 9, 1].sort() menghasilkan [1, 10, 9]. Selalu tulis (a, b) => a - b untuk bilangan. - Java: Timsort untuk objek, quicksort dwi-pivot untuk larik bilangan. C++: std::sort (introsort, tidak stabil) dan std::stable_sort.

Bagaimana mencari dan mengurutkan di Python, JavaScript, dan C++?

Tulis pencarian biner sekali dengan templat setengah terbuka dan pakai ulang; di Python pustaka standar sudah memilikinya sebagai bisect. Program pertama di bawah memuat batas bawah, pencarian selang tertutup yang menghitung berapa kali melihat, akar kuadrat bulat dengan mencari jawaban, dan perbandingan dengan bisect_left dan bisect_right. Program kedua memuat insertion sort (menghitung geserannya), merge sort, quicksort (menghitung perbandingannya), dan pengurutan stabil menurut kunci. Dua bilangan 9 dan 9 pada keluaran adalah inversi [5,2,4,6,1,3] dan geseran insertion sort: keduanya sama.

from bisect import bisect_left, bisect_right


def lower_bound(a, x):
    """The first index i with a[i] >= x, in the half-open form [lo, hi)."""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2      # never (lo + hi) // 2 with fixed-size integers
        if a[mid] < x:
            lo = mid + 1               # everything up to mid is too small
        else:
            hi = mid                   # mid itself might be the answer
    return lo


def find(a, x):
    """An index holding x (or -1) and the number of looks, in the closed form [lo, hi]."""
    lo, hi, looks = 0, len(a) - 1, 0
    while lo <= hi:
        looks += 1
        mid = lo + (hi - lo) // 2
        if a[mid] == x:
            return mid, looks
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, looks


def isqrt(n):
    """The largest r with r * r <= n: a binary search on the answer, no list needed."""
    lo, hi = 0, n
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # round up, so that lo = mid always makes progress
        if mid * mid <= n:
            lo = mid
        else:
            hi = mid - 1
    return lo


a = [1, 3, 3, 5, 7, 7, 7, 9, 12]
print(lower_bound(a, 7), bisect_left(a, 7), bisect_right(a, 7))
print(bisect_right(a, 7) - bisect_left(a, 7), lower_bound(a, 4), lower_bound(a, 100))
print(find(a, 5), find(a, 8))
print(isqrt(99), isqrt(100), isqrt(10 ** 12))
big = list(range(0, 2_000_000, 2))     # a million even numbers
print(find(big, 777_776), find(big, 777_777))
# 4 4 7
# 3 3 9
# (3, 4) (-1, 3)
# 9 10 1000000
# (388888, 19) (-1, 20)

def insertion(a):
    """Insertion sort; returns the sorted list and the number of shifts."""
    a, shifts = list(a), 0
    for i in range(1, len(a)):
        x, j = a[i], i - 1
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            shifts += 1
            j -= 1
        a[j + 1] = x
    return a, shifts


def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = (len(a) + 1) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= keeps equal keys in order: the sort is stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]


def quicksort(a, lo=0, hi=None):
    """In place, Lomuto partition, last element as the pivot. Returns the comparisons made."""
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return 0
    p, count = lo, 0
    for j in range(lo, hi):
        count += 1
        if a[j] < a[hi]:
            a[p], a[j] = a[j], a[p]
            p += 1
    a[p], a[hi] = a[hi], a[p]
    return count + quicksort(a, lo, p - 1) + quicksort(a, p + 1, hi)


def inversions(a):
    return sum(a[i] > a[j] for i in range(len(a)) for j in range(i + 1, len(a)))


x = [5, 2, 4, 6, 1, 3]
print(insertion(x), inversions(x))
print(merge_sort(x))
n = 200
print(quicksort(list(range(n))), n * (n - 1) // 2)            # sorted input: the worst case
data = [(i * 73) % n for i in range(n)]                        # a scrambled permutation of 0..199
print(quicksort(data), data == sorted(range(n)))
people = [("Ana", 30), ("Budi", 25), ("Citra", 30), ("Dewi", 25)]
print(sorted(people, key=lambda p: p[1]))                      # stable: Budi stays before Dewi
# ([1, 2, 3, 4, 5, 6], 9) 9
# [1, 2, 3, 4, 5, 6]
# 19900 19900
# 1409 True
# [('Budi', 25), ('Dewi', 25), ('Ana', 30), ('Citra', 30)]

;[10, 9, 1, 100].sort()                      // [1, 10, 100, 9]: no comparator means text order
;[10, 9, 1, 100].sort((a, b) => a - b)       // [1, 9, 10, 100]
const lowerBound = (a, x) => {
  let lo = 0, hi = a.length
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1)        // not (lo + hi) >> 1: see below
    if (a[mid] < x) lo = mid + 1
    else hi = mid
  }
  return lo
}
const a = [1, 3, 3, 5, 7, 7, 7, 9, 12]
;[7, 8, 100].map((x) => lowerBound(a, x))    // [4, 7, 9]
;(1500000000 + 2000000000) >> 1               // -397483648: the sum overflowed 32 bits
1500000000 + ((2000000000 - 1500000000) >> 1) // 1750000000

// bisection: halve a bracket on which f changes sign (60 would be enough for any bracket of doubles)
const f = (x) => x * x - 2
let lo = 1, hi = 2
for (let k = 0; k < 50; k++) {
  const mid = (lo + hi) / 2
  if (f(mid) * f(lo) <= 0) hi = mid
  else lo = mid
}
;[lo, hi, hi - lo]                           // [1.414213562373095, 1.4142135623730958, 8.88e-16]

#include <iostream>
#include <cstdio>
using namespace std;

int lowerBound(int a[], int n, int x) {
  int lo = 0, hi = n;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;                 // not (lo + hi) / 2: it can overflow
    if (a[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

int main() {
  int a[6] = {5, 2, 4, 6, 1, 3};
  int shifts = 0;
  for (int i = 1; i < 6; i++) {
    int x = a[i], j = i - 1;
    while (j >= 0 && a[j] > x) {
      a[j + 1] = a[j];
      shifts++;
      j--;
    }
    a[j + 1] = x;
  }
  for (int i = 0; i < 6; i++) printf("%d ", a[i]);
  printf("\n%d\n", shifts);                        // 9: the number of inversions

  int b[9] = {1, 3, 3, 5, 7, 7, 7, 9, 12};
  printf("%d %d %d\n", lowerBound(b, 9, 7), lowerBound(b, 9, 8), lowerBound(b, 9, 100));
  return 0;
}

/* output:
1 2 3 4 5 6
9
4 7 9
*/

Dari mana pencarian biner dan pengurutan berasal?

Pengurutan lebih tua daripada komputer, karena mesin sensus dan bank memerlukannya, dan pencarian biner ternyata terkenal mudah salah ditulis.

• 1890-an–1900-an. Mesin kartu berlubang Herman Hollerith mentabulasi sensus Amerika Serikat 1890, dan pengurut kartu yang menyusul mengurutkan satu kolom sekali waktu, gagasan radix sort.
• 1945. John von Neumann menulis merge sort untuk EDVAC, program pengurutan pertama untuk komputer program tersimpan.
• 1946. John Mauchly menguraikan pencarian biner dalam rangkaian kuliah tentang komputasi di Moore School; itulah uraian tertua yang diterbitkan.
• 1959. Donald Shell menerbitkan Shellsort, pengurutan pertama yang diketahui mengalahkan n^2 dengan membandingkan elemen yang berjauhan. Pada tahun yang sama Tony Hoare menemukan quicksort, ketika bekerja di Moskow pada penerjemahan mesin; ia menerbitkannya pada 1961.
• 1962. Menurut Knuth, pencarian biner pertama yang diterbitkan dan benar untuk setiap panjang daftar muncul, enam belas tahun sesudah yang pertama.
• 1964. J. W. J. Williams menerbitkan heapsort, dan Robert Floyd segera menunjukkan cara membangun heap dalam waktu linear.
• 1997. David Musser merancang introsort, quicksort yang tidak dapat memburuk.
• 2002. Tim Peters menulis Timsort untuk Python, dan kemudian ia menyebar ke Java, Android, dan mesin JavaScript.
• 2006. Joshua Bloch menunjukkan bahwa titik tengah yang dihitung sebagai (lo + hi) / 2 dalam pencarian biner dan merge sort pustaka Java dapat meluap untuk daftar lebih dari 2^30 elemen.

Kesalahan apa yang sering terjadi pada pencarian dan pengurutan?

Kesalahan paling umum pada pencarian biner dan pengurutan adalah sembilan hal berikut, masing-masing dengan pernyataan yang benar.

Latihan: uji pemahamanmu

Soal-soal ini mencampur semua yang dibahas di atas. Jika jawabanmu belum tepat, perhatikan petunjuk yang tersedia, lalu coba kembali.

Ringkasan: pencarian biner dan pengurutan sekilas

• Pencarian biner: daftar terurut, lihat bagian tengah, buang separuh; paling banyak \lfloor\log_2n\rfloor+1 kali melihat.
• Pertanyaan posisi: templat setengah terbuka memberi batas bawah (a[i]\ge x pertama); ubah < menjadi <= untuk batas atas; selisihnya menghitung salinan.
• Galat: pertahankan satu konvensi dengan invariannya, dan pakai lo + (hi - lo) / 2.
• Cari jawabannya: pertanyaan ya atau tidak yang monoton apa pun; akar bulat dalam \log_2N pengujian; bisection memperoleh satu angka biner per langkah dan tidak dapat gagal.
• Pengurutan sederhana: sekitar (n^2)/(2) langkah; bubble dan insertion sort bergerak tepat sebanyak inversi.
• Merge sort: paling banyak n\lceil\log_2n\rceil perbandingan, memori tambahan O(n), stabil. Quicksort: ≈1,39 n\log_2n rata-rata, (n(n-1))/(2) untuk pivot ekstrem, di tempat, tidak stabil.
• Batas: pengurutan perbandingan memerlukan \log_2(n!)≈ n\log_2n-1,44n perbandingan; counting dan radix sort menghindari perbandingan.
• Dalam praktik: pakai pengurutan pustaka (Timsort, introsort), yang stabil untuk beberapa kunci, dan pembanding untuk bilangan di JavaScript.

Glosarium: istilah penting

Pencarian biner

Pencarian dalam daftar terurut yang melihat elemen tengah dan membuang separuh yang tidak mungkin memuat target.

Invarian

Pernyataan yang benar sebelum dan sesudah setiap langkah perulangan, yang dari situ kebenaran perulangan dibuktikan.

Batas bawah (posisi)

Indeks pertama yang elemennya sedikitnya x; untuk x yang tidak ada ia adalah titik sisip yang menjaga daftar tetap terurut.

Metode bisection

Cara mencari akar fungsi kontinu dengan berulang kali membagi dua selang yang di ujung-ujungnya fungsi itu berlawanan tanda.

Inversi

Pasangan posisi dalam daftar dengan elemen awal lebih besar daripada elemen akhir; daftar terurut tidak memilikinya.

Pengurutan stabil

Pengurutan yang mempertahankan elemen berkunci sama dalam urutan yang dimilikinya sebelum diurutkan.

Pengurutan di tempat

Pengurutan yang menata ulang daftar dengan hanya sedikit memori tambahan.

Pivot

Elemen yang dipilih quicksort agar elemen yang lebih kecil dipindahkan ke depannya dan yang lain ke belakangnya.

Pengurutan perbandingan

Pengurutan yang mengetahui urutan hanya dengan membandingkan dua elemen sekali waktu, sehingga memerlukan sekitar n log n perbandingan.

Timsort

Hibrida stabil dari merge sort dan insertion sort yang dipakai Python dan Java untuk objek, cepat pada data yang sebagian terurut.

Pertanyaan yang sering diajukan

Referensi

1. Donald E. Knuth (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.), sections 5 and 6.2.1. Addison-Wesley.
2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2022). Introduction to Algorithms (4th ed.), chapters 2, 6, 7 and 8: Getting Started; Heapsort; Quicksort; Sorting in Linear Time. MIT Press.
3. C. A. R. Hoare (1961). Algorithm 64: Quicksort. Communications of the ACM 4(7).
4. Joshua Bloch (2006). Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Google Research Blog.
5. Jon Bentley (1999). Programming Pearls (2nd ed.), column 4: Writing Correct Programs. Addison-Wesley.

Artikel terkait

• Notasi Big-O: Notasi Big-O dijelaskan: definisi, laju pertumbuhan dari O(1) sampai O(n!), menghitung langkah dalam kode, kasus terbaik dan terburuk, rekurensi, dan teorema Master.
• Metode Newton: Metode Newton untuk menyelesaikan f(x) = 0: rumus dari garis singgung, contoh, konvergensi kuadrat, kapan gagal, akar kuadrat dengan tangan, dan kode.
• Bilangan Floating-Point: Cara kerja bilangan floating-point: bit IEEE 754, jarak dan pembulatan, NaN dan tak hingga, galat yang menumpuk, pembatalan, perbandingan, dan tipe yang dipakai.
• Bilangan Biner: Konversi, Operasi, Bit, dan Komplemen Dua: Bilangan biner: bit dan nilai tempat, konversi ke desimal dan heksadesimal, aritmetika biner, komplemen dua, operator bitwise, dan pecahan biner.