Searching Dalam Python

Halloo semuaa!!….

Saya Aufa Abid Rahman Nashir, saya adalah mahasiswa prodi S1 Teknologi Informasi di Universitas Tidar. Pada pertemuan kali ini kita akan mempelajari tentang Searching dalam Python.

Sebelum ke pembahasan di sini saya akan menyebutkan beberapa tujuan dari praktikum pada pertemuan ini.

Tujuan

• Mahasiswa mampu menerapkan berbagai algoritma Searching pada bahasa pemrograman Python secara tepat.
• Mahasiswa mampu menyelesaikan studi kasus pencarian data dalam array.

Pendahuluan

Pendahuluan

Dalam pengolahan data, proses pencarian merupakan salah satu operasi dasar yang sangat penting dalam pemrograman. Pencarian digunakan untuk menemukan suatu nilai tertentu di dalam kumpulan data seperti array atau list. Dalam bahasa pemrograman Python, terdapat berbagai algoritma pencarian yang dapat digunakan dengan karakteristik dan tingkat efisiensi yang berbeda-beda. Oleh karena itu, pemahaman terhadap algoritma pencarian menjadi hal yang penting bagi seorang programmer agar dapat memilih metode yang paling sesuai dengan kebutuhan.

Pada praktikum ini, dilakukan pembelajaran mengenai beberapa algoritma pencarian yaitu Linear Search, Binary Search, dan Jump Search. Setiap algoritma memiliki cara kerja serta keunggulan masing-masing dalam menyelesaikan permasalahan pencarian data.

Linear Search merupakan metode pencarian paling sederhana yang dilakukan dengan cara memeriksa setiap elemen dalam array secara berurutan hingga elemen yang dicari ditemukan. Metode ini tidak memerlukan data yang terurut, namun memiliki kelemahan dalam hal efisiensi karena kompleksitas waktunya mencapai O(n).

Binary Search adalah metode pencarian yang bekerja pada data yang telah terurut. Algoritma ini membagi data menjadi dua bagian dan menentukan posisi pencarian berdasarkan nilai tengah. Dengan pendekatan ini, Binary Search memiliki kompleksitas waktu yang lebih cepat yaitu O(log n).

Jump Search merupakan pengembangan dari Linear Search dengan konsep melompati beberapa elemen sekaligus untuk mempercepat pencarian. Algoritma ini bekerja pada data yang sudah terurut dan menggunakan ukuran langkah tertentu, biasanya sebesar akar dari jumlah data.

1. Linear Search

Linear Search bekerja dengan cara menelusuri seluruh elemen dalam array satu per satu hingga menemukan nilai yang dicari. Jika nilai ditemukan, maka indeks akan dikembalikan, jika tidak maka hasil pencarian adalah tidak ditemukan.

def LinearSearch(arr, N, x):

    for i in range(0, N):
        if (arr[i] == x):
            return i
    return -1

# Driver Code
if __name__ == "__main__":
    arr = [20, 10, 30, 50, 40]
    x = 10
    N = len(arr)

    # Function Call
    result = LinearSearch(arr, N, x)
    if(result == -1):
        print("Element yang dicari tidak ada dalam array")
    else:
        print("Element yang dicari berada pada indeks ke -",result)

output

Linear Search cocok digunakan untuk dataset kecil dan data yang tidak terurut. Namun, untuk data dalam jumlah besar, metode ini kurang efisien.

2. Binary Search

Binary Search merupakan algoritma pencarian yang digunakan pada data yang telah terurut. Metode ini bekerja dengan membagi ruang pencarian menjadi dua bagian secara berulang hingga data yang dicari ditemukan. Dengan cara ini, Binary Search memiliki efisiensi yang tinggi dengan kompleksitas waktu O(log n).

a. Binary Search Iteratif

Metode iteratif menggunakan perulangan (loop) untuk mempersempit ruang pencarian hingga elemen ditemukan atau tidak ditemukan.

# It returns location of x in given array arr
def binarySearch(arr, l, r, x):

    while l <= r:

        mid = l + (r - l) // 2

        # Check if x is present at mid
        if arr[mid] == x:
            return mid

        # If x is greater, ignore left half
        elif arr[mid] < x:
            l = mid + 1

        # If x is smaller, ignore right half
        else:
            r = mid - 1

    # If we reach here, then the element
    # was not present
    return -1

# Driver Code
if __name__ == '__main__':
    arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
    x = 72

    # Function call
    result = binarySearch(arr, 0, len(arr)-1, x)
    if result != -1:
        print("Element is present at index", result)
    else:
        print("Element is not present in array")

output

Metode ini lebih sederhana dan tidak memerlukan pemanggilan fungsi berulang, sehingga penggunaan memori lebih efisien.

b. Binary Search Rekursif

Metode rekursif menggunakan pemanggilan fungsi secara berulang hingga kondisi terpenuhi.

# Returns index of x in arr if present, else -1
def binarySearch(arr, l, r, x):

    # Check base case
    if r >= l:

        mid = l + (r - l) // 2

        # If element is present at the middle itself
        if arr[mid] == x:
            return mid

        # If element is smaller than mid, then it
        # can only be present in left subarray
        elif arr[mid] > x:
            return binarySearch(arr, l, mid-1, x)

        # Else the element can only be present
        # in right subarray
        else:
            return binarySearch(arr, mid + 1, r, x)

    # Element is not present in the array
    else:
        return -1

# Driver Code
if __name__ == '__main__':
    arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
    x = 72

    # Function call
    result = binarySearch(arr, 0, len(arr)-1, x)

    if result != -1:
        print("Element terdapat pada indeks ke-", result)
    else:
        print("Element tidak ada dalam array")

output

Metode rekursif lebih elegan dalam penulisan, namun menggunakan lebih banyak memori karena adanya pemanggilan fungsi berulang.

3. Jump Search

Jump Search bekerja dengan melompati beberapa elemen dalam array untuk menemukan rentang lokasi data yang dicari, kemudian dilanjutkan dengan pencarian linier pada rentang tersebut.

import math

def jumpSearch( arr , x , n ):

    # Finding block size to be jumped
    step = math.sqrt(n)

    # Finding the block where element is
    # present (if it is present)
    prev = 0
    while arr[int(min(step, n)-1)] < x:
        prev = step
        step += math.sqrt(n)
        if prev >= n:
            return -1

    # Doing a linear search for x in
    # block beginning with prev.
    while arr[int(prev)] < x:
        prev += 1

        # If we reached next block or end
        # of array, element is not present.
        if prev == min(step, n):
            return -1

    # If element is found
    if arr[int(prev)] == x:
        return prev

    return -1

# Driver code to test function
arr = [ 0, 1, 1, 2, 3, 5, 8, 13, 21,
      34, 55, 89, 144, 233, 377, 610 ]
x = 55
n = len(arr)

# Find the index of 'x' using Jump Search
index = jumpSearch(arr, x, n)

# Print the index where 'x' is located
print("Number" , x, "is at index" , "%.0f"%index)

output

Jump Search memiliki performa yang lebih baik dibandingkan Linear Search, namun masih berada di bawah Binary Search dalam hal efisiensi.

Studi Kasus 1

Pada studi kasus ini, dilakukan pencarian nilai minimum dan maksimum dari sekumpulan data mahasiswa menggunakan pendekatan Linear Search. Metode ini dilakukan dengan membandingkan setiap elemen dalam array untuk menemukan nilai terkecil dan terbesar.

# Python program of above implementation
# structure is used to return two values from minMax()
class pair:
    def __init__(self):
        self.min = 0
        self.max = 0

def getMinMax(arr: list, n: int) -> pair:
    minmax = pair()

    # If there is only one element then return it as min and max both
    if n == 1:
        minmax.max = arr[0]
        minmax.min = arr[0]
        return minmax

    # If there are more than one elements, then initialize min and max
    if arr[0] > arr[1]:
        minmax.max = arr[0]
        minmax.min = arr[1]
    else:
        minmax.max = arr[1]
        minmax.min = arr[0]

    for i in range(2, n):
        if arr[i] > minmax.max:
            minmax.max = arr[i]
        elif arr[i] < minmax.min:
            minmax.min = arr[i]

    return minmax

# Driver Code
if __name__ == "__main__":
    arr = [1000, 11, 445, 1, 330, 3000]
    arr_size = 6
    minmax = getMinMax(arr, arr_size)
    print("Minimum element is", minmax.min)
    print("Maximum element is", minmax.max)

output

Melalui metode ini, proses pencarian dilakukan secara sederhana namun efektif untuk dataset kecil hingga menengah.

Studi Kasus 2

Pada studi kasus ini, diberikan sebuah array yang berisi angka dari 1 hingga n, namun terdapat satu angka yang hilang dan satu angka yang muncul dua kali. Permasalahan ini dapat diselesaikan dengan bantuan array tambahan untuk melacak kemunculan setiap elemen.

def printTwoElements(arr):
    n = len(arr)
    # Creating temp array of size n with initial values as 0.
    temp = [0] * n 
    repeatingNumber = -1
    missingNumber = -1

    for i in range(n):
        temp[arr[i] - 1] += 1
        if temp[arr[i] - 1] > 1:
            repeatingNumber = arr[i]

    for i in range(n):
        if temp[i] == 0:
            missingNumber = i + 1
            break

    print("The repeating number is", repeatingNumber, ".")
    print("The missing number is", missingNumber, ".")

# Driver Code
arr = [7, 3, 4, 5, 5, 6, 2]
printTwoElements(arr)

output

Pendekatan ini memanfaatkan pencatatan frekuensi untuk mendeteksi elemen yang tidak muncul dan elemen yang muncul lebih dari satu kali.

Studi Kasus 3

Pada studi kasus ini, diberikan array yang telah terurut namun mengalami rotasi. Tugasnya adalah menentukan apakah terdapat dua elemen yang jika dijumlahkan menghasilkan nilai tertentu.

def pairsInSortedRotated(arr, n, x):
    # 1. Temukan titik pivot (elemen terbesar)
    for i in range(0, n - 1):
        if arr[i] > arr[i + 1]:
            break

    # l = indeks elemen terkecil, r = indeks elemen terbesar
    r = i
    l = (i + 1) % n

    # 2. Two pointers untuk mencari pasangan
    while l != r:
        if arr[l] + arr[r] == x:
            return True

        elif arr[l] + arr[r] < x:
            l = (l + 1) % n
        else:
            r = (n + r - 1) % n

    return False

# Driver Code
arr1 = [11, 15, 6, 8, 9, 10]
x1 = 16

arr2 = [11, 15, 26, 38, 9, 10]
x2 = 35

for arr, x in [(arr1, x1), (arr2, x2)]:
    n = len(arr)
    if pairsInSortedRotated(arr, n, x):
        print("Output: true")
        print("Explanation: Terdapat pasangan dengan jumlah", x)
    else:
        print("Output: false")
        print("Explanation: Tidak ada pasangan dengan jumlah", x)
    print()

output

Metode ini memanfaatkan sifat array yang telah terurut dan diputar untuk melakukan pencarian pasangan secara efisien tanpa harus memeriksa semua kemungkinan kombinasi.

Kesimpulan

Algoritma pencarian merupakan bagian penting dalam pengolahan data karena digunakan untuk menemukan informasi tertentu dalam suatu kumpulan data. Linear Search merupakan metode yang sederhana dan fleksibel namun kurang efisien untuk data besar. Binary Search menawarkan efisiensi yang lebih tinggi dengan syarat data harus terurut. Sementara itu, Jump Search menjadi alternatif yang lebih cepat dibandingkan Linear Search namun masih di bawah Binary Search.

Pemilihan algoritma pencarian yang tepat sangat bergantung pada kondisi data dan kebutuhan sistem. Dengan memahami karakteristik masing-masing algoritma, seorang programmer dapat menentukan metode yang paling optimal untuk digunakan.

[embed]Struktur-Data/Pertemuan-5/StrukturData_Pertemuan_5.ipynb at main · Aufanashr/Struktur-Data Contribute to Aufanashr/Struktur-Data development by creating an account on GitHub.github.com

Terimakasihh…