Pencarian Bagi Dua (Binary Search)

Syarat : Data harus terurut Salah satu keuntungan data yang terurut adalah memudahkan pencarian, yang dalam hal ini adalah pencarian bagi dua. Sebenarnya dalam kehidupan sehari-hari kita sering menerapkan algoritma ini. Untuk mencari kata tertentu dalam kamus (misalnya kamus bahasa Inggris), kita tidak membuka kamus tersebut dari halaman awal sampai halaman akhir satu persatu, namun kita mencarinya dengan cara membelah atau membagi halaman-halaman buku tersebut. Begitu seterusnya sampai kita menemukan kata yang dicari.

Algoritma pencarian bagidua

81	76	21	18	16	13	10	7
Ia=1	2	3	4	5	6	7	8=ib

1.Misal elemen yang dicari adalah X = 18
langkah 1:
ia=1 dan ib=8 elemen tengah K=(1+8)/2 = 4 (diarsir)

Langkah 2: 

L[4]=18? Ya! (X ditemukan, pencarian dihentikan).

16	13	10	7
5	6	7	8

Langkah 2.1: 

ia = 5 dan ib = 8
elemen tengah K = (5+8)/2 = 6 (diarsir)

16	13	10	7
5	6	7	8

        Kiri                                                           Kanan

Langkah 2.2: 

L[6] = 16? Tidak !
harus diputuskan apakan pencarian akan dilakukan di bagian kiri atau kanan dengan pemeriksaan sbb:
L[6] > 16 ? Tidak ! Lakukan pencarian pada larik bagian kiri dengan ia= 5 dan ib = k-1 = 5

Contoh

#include <iostream>

#include <conio>

int main() {

const int arraySize = 5;

int target;

// Array size and values already known.

int array[arraySize] = {1, 2, 3, 4, 5};

int first, mid, last;

cout << "Enter a target to be found: ";

cin >> target;

// Initialize first and last variables.

first = 0;

last = 2;