Python - Algoritma Pencarian

Pencarian adalah kebutuhan yang sangat mendasar saat Anda menyimpan data dalam struktur data yang berbeda. Penilaian paling sederhana adalah dengan memeriksa setiap elemen dalam struktur data dan mencocokkannya dengan nilai yang Anda cari. Ini dikenal sebagai pencarian Linear. Ini tidak efisien dan jarang digunakan, tetapi membuat program untuknya memberikan gambaran tentang bagaimana kita dapat mengimplementasikan beberapa algoritma pencarian lanjutan.

Pencarian Linear

Dalam jenis pencarian ini, pencarian berurutan dilakukan atas semua item satu per satu. Setiap item dicentang dan jika kecocokan ditemukan maka item tertentu dikembalikan, jika tidak pencarian berlanjut hingga akhir struktur data.

def linear_search(values, search_for):
    search_at = 0
    search_res = False

# Match the value with each data element	
    while search_at < len(values) and search_res is False:
        if values[search_at] == search_for:
            search_res = True
        else:
            search_at = search_at + 1

    return search_res

l = [64, 34, 25, 12, 22, 11, 90]
print(linear_search(l, 12))
print(linear_search(l, 91))

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

True
False

Pencarian Interpolasi

Algoritma pencarian ini bekerja pada posisi probing dari nilai yang dibutuhkan. Agar algoritme ini berfungsi dengan baik, pengumpulan data harus dalam bentuk yang diurutkan dan didistribusikan secara merata. Awalnya, probe position adalah posisi item paling tengah dari koleksi. Jika terjadi kecocokan, maka indeks item dikembalikan. Jika item tengah lebih besar dari item, maka posisi probe dihitung lagi di sub-larik di sebelah kanan item tengah. Jika tidak, item akan dicari di subarray di sebelah kiri item tengah. Proses ini berlanjut pada sub-larik juga sampai ukuran sub-larik berkurang menjadi nol.

Ada rumus khusus untuk menghitung posisi tengah yang ditunjukkan pada program di bawah ini.

def intpolsearch(values,x ):
    idx0 = 0
    idxn = (len(values) - 1)

    while idx0 <= idxn and x >= values[idx0] and x <= values[idxn]:

# Find the mid point
	mid = idx0 +\
               int(((float(idxn - idx0)/( values[idxn] - values[idx0]))
                    * ( x - values[idx0])))

# Compare the value at mid point with search value 
        if values[mid] == x:
            return "Found "+str(x)+" at index "+str(mid)

        if values[mid] < x:
            idx0 = mid + 1
    return "Searched element not in the list"


l = [2, 6, 11, 19, 27, 31, 45, 121]
print(intpolsearch(l, 2))

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

Found 2 at index 0