Linear dan Binary Search

LINEAR DAN BINARY SEARCH

 Dalam algoritma pemrograman, ada banyak kasus di mana kita diharuskan mencari suatu value dalam kumpulan data. Misal dalam dunia nyata, kita memiliki 20 buah kelereng, kemudian kita cari kelereng mana yang memiliki tepat n buah di dalamnya.

Untuk melakukan sebuah pencarian, atau search, harus memiliki ketiga kriteria ini:

1. Teknik/algoritma search
2. Value/nilai yang dicari
3. Search space (ruang batas pencarian)

   Dalam contoh di atas, teknik pencarian bisa menggunakan linear search atau teknik lainnya. Value yang dicari adalah kelereng dengan n buah . Dan search space-nya adalah 20 buah kelereng yang kita miliki.

Dalam post ini hanya akan dibahas mengenai Linear Search dan Binary Search.

Linear Search

Linear search atau metode pencarian linear adalah teknik pencarian di mana program akan mencari anggota dari suatu search space satu per satu sampai value yang dicari ditemukan. Kompleksitas pencarian adalah O(n).

Linear search juga merupakan program search yang mudah dipahami, linear search memiliki kelebihan apabila data yang di cari letaknya pada data – data awal sehingga prosesnya berjalan cepat, namun apabila data yang di cari letaknya pada data terakhir maka pencarian lebih memakan waktu yang cukup lama pula.
#SEARCHING DARI KANAN KE KIRI(DARI LEN-1 KE 0)
search = 4
mylist = [1,2,3,4,5,6]
position = len(mylist)-1#first/awal
last = 0#akhir
found = False
while position >= last and not found:#lebih besar dari
    if mylist[position] == search:
        found = True
    else:
        position = position-1#DECREMENT
    if found:
        print("Found the search number =>",search)
        print("pada posisi ke -",position)
    else:
        print("Did not find the search number.")

 

 

Binary Search

Binary search adalah metode pencarian dalam suatu search space (atau lebih sering arrays) yang telah terurut isinya, baik terurut menaik maupun menurun. 

Binary search, bisa dilakukan jika data sudah terurut, dimana sistem pencariannya yang relatif cepat dan efisien walaupun ada banyak data sekalipun. Karena data dicari dari depan, tengah dan belakang. Tetapi sintaks dan algoritmanya sedikit lebih rumit, karena kita harus mengurutkan data terlebih dahulu. Pengurutan data disini bisa kalian lakukan dengan metode ascending ataupun descending.

Untuk dasar dari binary search ini, saya akan memberikan array dengan data yang telah diurut sebelumnya. Agar lebih mudah memahami dasar dari binary search ini. Adapun algoritma dari binary search ini adalah sebagai berikut :

1. Membaca data yang ada di array, jika data belum terurut, maka lakukan pengurutan data.
2. Menentukan data yang akan dicari di dalam array.
3. Menentukan nilai elemen tengah array, jika nilai elemen tengah array sama dengan data yang dicari, maka pencarian akan dihentikan, jika elemen tengah tidak sama dengan data yang dicari, maka:
• Jika nilai tengah lebih besar dari nilai yang dicari, maka pencarian hanya dilakukan pada setengah array pertama.

Jika nilai tengah lebih kecil dari nilai yang dicari, maka pencarian hanya dilakukan pada setengah array sisa. 

#BINARY SEARCH
search = 9
mylist = [3,1,9,7,5,6]
mylist.sort()
first= 0
last = len(mylist)-1

found = False
counter = 0

while first <= last and not found :
    middle = (first + last)//2

    if mylist[middle] == search:
       
        found = True
    else :
        if search < mylist[middle]:
            last = middle -1
        else:
            first = middle +1
           
        counter = counter +1
    if found:
        print (
            "Found the search number.")
        print("pada indeks ke-",middle)
    else:
        print("Did not find the search number.")

print(search)