Làm thế nào để bạn viết một tìm kiếm tuyến tính trong python?

Tuần trước, chúng tôi đã mô tả tìm kiếm nhị phân trong Python. Trong hướng dẫn này, chúng ta sẽ làm điều tương tự với một thuật toán tìm kiếm mới. thuật toán tìm kiếm tuyến tính

Thuật toán tìm kiếm tuyến tính là một trong những thuật toán tìm kiếm đơn giản nhất. Đầu vào của thuật toán tìm kiếm tuyến tính là một mảng hoặc danh sách và một mục. Thuật toán tìm kiếm sự hiện diện của phần tử bên trong mảng. Nếu mục được tìm thấy, chỉ mục của mục được trả về. Mặt khác, nó có thể trả về null hoặc bất kỳ giá trị nào khác mà bạn cho rằng không thể tồn tại bên trong mảng

Dưới đây là các bước cơ bản để thực hiện thuật toán tìm kiếm tuyến tính trong Python

1. Tìm kiếm mục đầu vào tại chỉ mục đầu tiên (chỉ số 0) của mảng
2. Kiểm tra xem mục có được tìm thấy tại chỉ mục hiện tại không. Nếu có, trả lại chỉ mục và chuyển sang bước 5
3. Kiểm tra xem chỉ mục hiện tại có phải là chỉ mục cuối cùng của mảng không. Nếu có, trả về null và chuyển sang bước 5
4. Di chuyển đến chỉ mục tiếp theo trong mảng và chuyển sang bước 2
5. Dừng thuật toán

Chạy khô thuật toán Tìm kiếm tuyến tính

Trước khi chúng tôi triển khai thuật toán tìm kiếm tuyến tính trong Python, hãy thử tìm hiểu logic của thuật toán tìm kiếm tuyến tính bằng một ví dụ

Giả sử chúng ta có một danh sách các số nguyên và chúng ta muốn tìm kiếm số nguyên 15 trong danh sách. Thiết lập Python của bạn có thể trông giống như thế này

nums = [4,9,15,21,25,28,35,38,40,45]

item = 15

lặp lại 1

Bước 1. Tìm kiếm mục 15 tại chỉ mục thứ 0 của thenumsarray

Bước 2. Kiểm tra xem 15 có tồn tại ở chỉ mục hiện tại không (chỉ mục 0). Điều này sẽ không trả về true vì chỉ mục hiện tại chứa mục 4. Vì vậy, chúng tôi chuyển sang bước 3

Bước 3. Kiểm tra xem chỉ mục hiện tại có phải là chỉ mục cuối cùng của thenumsarray không. Vì điều này cũng trả về false, chúng tôi chuyển sang bước tiếp theo

Bước 4. Di chuyển đến chỉ mục 1 của thenumsarray và chuyển sang bước lặp tiếp theo, bắt đầu từ bước thứ hai

lặp lại 2

Bước 2. Kiểm tra xem 15 có tồn tại ở chỉ mục hiện tại không (chỉ mục 1). Điều này sẽ không trả về true vì chỉ mục hiện tại chứa mục 9. Vì vậy, chúng tôi chuyển sang bước 3

Bước 3. Kiểm tra xem chỉ mục hiện tại có phải là chỉ mục cuối cùng của thenumsarray không. Vì điều này trả về false, chúng tôi chuyển sang bước tiếp theo

Bước 4. Di chuyển đến chỉ mục 2 của thenumsarray và chuyển sang bước lặp tiếp theo, bắt đầu từ bước thứ hai

lặp lại 3

Bước 2. Kiểm tra xem 15 có tồn tại ở chỉ mục hiện tại không (chỉ mục 2). Điều này sẽ trả về true vì chỉ mục hiện tại chứa mục 15. Chỉ số 2 sẽ được trả về hàm gọi và chúng ta chuyển sang bước 5

Bước 5. Dừng thuật toán

Nhận miễn phí Bộ công cụ dành cho nhà phát triển Python của chúng tôi

Tôi đã tập hợp Bộ công cụ dành cho nhà phát triển Python với hơn 100 tập lệnh Python dựng sẵn bao gồm cấu trúc dữ liệu, Pandas, NumPy, Seaborn, máy học, xử lý tệp, quét web và nhiều thứ khác - và tôi muốn bạn có bộ công cụ này miễn phí. Nhập địa chỉ email của bạn dưới đây và tôi sẽ gửi một bản sao theo cách của bạn

Có, tôi sẽ lấy Bộ công cụ dành cho nhà phát triển Python miễn phí

Ngôn ngữ lập trình

• VBA
• con trăn

Triển khai thuật toán tìm kiếm tuyến tính trong Python

Vì logic của thuật toán tìm kiếm tuyến tính thực sự đơn giản, nên việc triển khai thuật toán tìm kiếm tuyến tính trong Python cũng đơn giản như vậy. Chúng tôi tạo một vòng lặp for lặp qua mảng đầu vào. Nếu mục được tìm thấy tại bất kỳ chỉ mục nào của mảng, chỉ mục mảng đó được in và chúng ta có thể ngắt vòng lặp for. Mặt khác, nếu vòng lặp for kết thúc và mục không được tìm thấy, chúng ta có thể in ra rằng mục không được tìm thấy

Đây là một triển khai phi chức năng của thuật toán tìm kiếm tuyến tính trong Python

nums = [4,9,15,21,25,28,35,38,40,45]

item = 38


value_found = False

for i in range(len(nums)):

    if nums[i] == item:
        value_found = True
        print("Item found at index ", i)
        break

if value_found == False:
    print("Item not found")

đầu ra

Item found at index  7

Và đây là một chức năng thực hiện của thuật toán tìm kiếm tuyến tính. Hàm lin_search() trong tập lệnh sau chấp nhận một mảng đầu vào và mục được tìm kiếm làm tham số của nó

Bên trong hàm, vòng lặp for lặp qua tất cả các mục của mảng đầu vào. Nếu mục được tìm thấy ở bất kỳ chỉ mục nào, giá trị chỉ mục được trả về. Nếu không, giá trị Null được trả về

def lin_search(nums, item):

    for i in range(len(nums)):

        if nums[i] == item:
            value_found = True
            return i

    return None


nums = [4,9,15,21,25,28,35,38,40,45]

item = 40

index = lin_search(nums, item)
if index != None:
    print("Item found at index", index)
else:
    print("Item not found")

đầu ra

Item found at index 8

Độ phức tạp về thời gian của thuật toán tìm kiếm tuyến tính là N trong đó N là số mục trong mảng đầu vào. Đây là trường hợp mục được tìm thấy ở chỉ mục cuối cùng của mảng đầu vào sau khi lặp qua tất cả các mục của mảng

Rõ ràng, thuật toán tìm kiếm tuyến tính không phải là cách hiệu quả nhất để tìm vị trí của phần tử trong danh sách, nhưng học cách lập trình logic của tìm kiếm tuyến tính vẫn là một kỹ năng hữu ích trong Python hoặc bất kỳ ngôn ngữ lập trình nào khác. Nếu bạn thấy điều này hữu ích và muốn có thêm một số ví dụ về lập trình Python, hãy nhập địa chỉ email của bạn vào bên dưới

Tìm kiếm tuyến tính hoạt động như thế nào trong Python?

Một ví dụ về tìm kiếm tuyến tính là gì?

Cú pháp tìm kiếm tuyến tính là gì?