Python - Thuật toán tìm kiếm

Tìm kiếm là một nhu cầu rất cơ bản khi bạn lưu trữ dữ liệu trong các cấu trúc dữ liệu khác nhau. Cách thẩm định đơn giản nhất là xem xét mọi phần tử trong cấu trúc dữ liệu và khớp nó với giá trị bạn đang tìm kiếm. Đây được gọi là tìm kiếm tuyến tính. Nó không hiệu quả và hiếm khi được sử dụng, nhưng việc tạo một chương trình cho nó mang lại ý tưởng về cách chúng ta có thể triển khai một số thuật toán tìm kiếm nâng cao.

Tìm kiếm tuyến tính

Trong kiểu tìm kiếm này, tìm kiếm tuần tự được thực hiện trên tất cả các mục một. Mọi mục đều được kiểm tra và nếu tìm thấy khớp thì mục cụ thể đó sẽ được trả lại, nếu không thì việc tìm kiếm tiếp tục cho đến khi kết thúc cấu trúc dữ liệu.

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))

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

True
False

Tìm kiếm nội suy

Thuật toán tìm kiếm này hoạt động trên vị trí thăm dò của giá trị được yêu cầu. Để thuật toán này hoạt động bình thường, việc thu thập dữ liệu phải ở dạng được sắp xếp và phân bổ đều. Ban đầu, vị trí thăm dò là vị trí của vật phẩm chính giữa nhất của bộ sưu tập, nếu khớp xảy ra thì chỉ số của vật phẩm đó sẽ được trả về. Nếu mục ở giữa lớn hơn mục, thì vị trí thăm dò lại được tính trong mảng con bên phải của mục giữa. Nếu không, mục sẽ được tìm kiếm trong mảng con bên trái mục giữa. Quá trình này cũng tiếp tục trên mảng con cho đến khi kích thước của mảng con giảm xuống 0.

Có một công thức cụ thể để tính toán vị trí giữa được chỉ ra trong chương trình bên dưới.

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))

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

Found 2 at index 0