Pencarian berurut dan pencarian biner

Pencarian berurut memeriksa data satu per satu dari awal sampai yang dicari ditemukan atau datanya habis. Cara ini berjalan pada data dalam urutan apa pun, dan pada daftar berisi seribu data bisa memerlukan seribu pemeriksaan. Pencarian biner memeriksa data di tengah, lalu membuang separuh wilayah yang pasti tidak memuat targetnya, dan mengulanginya. Pada seribu data, sepuluh pemeriksaan sudah cukup.

Harga dari kecepatan itu adalah satu syarat keras: datanya harus sudah urut. Modul bisect menyediakan bisect_left yang mengembalikan titik sisip, yaitu posisi tempat sebuah nilai dapat ditaruh tanpa merusak urutan. Titik sisip itu dipakai untuk dua hal: menyisipkan data baru, dan memeriksa apakah sebuah nilai sudah ada dengan membandingkan isi pada posisi tersebut.

from bisect import bisect_left

suhu = [21, 24, 27, 30]
print(bisect_left(suhu, 27))   # 2, posisi 27 sekarang
print(bisect_left(suhu, 26))   # 2, tempat 26 akan disisipkan

Cara yang sama dipakai basis data. Dokumentasi perencana kueri SQLite menjelaskan bahwa kueri yang dapat memakai indeks dijawab dengan pencarian biner pada indeks itu, bukan dengan membaca seluruh tabel. Indeks pada basis data adalah salinan kolom yang disimpan dalam keadaan urut, persis syarat yang sama.