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

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

Thuật toán Tìm kiếm tuyến tính tìm kiếm trong một mảng và trả về chỉ mục của giá trị mà nó tìm kiếm.

Chạy mô phỏng ở trên để xem thuật toán Tìm kiếm tuyến tính hoạt động như thế nào.

Để xem điều gì xảy ra khi không tìm thấy giá trị, hãy thử tìm giá trị 5.

Thuật toán này rất đơn giản, dễ hiểu và dễ thực hiện.

Nếu mảng đã được sắp xếp, tốt hơn là sử dụng thuật toán Tìm kiếm nhị phân nhanh hơn nhiều mà chúng ta sẽ khám phá ở trang tiếp theo.

Sự khác biệt lớn giữa thuật toán sắp xếp và thuật toán tìm kiếm là thuật toán sắp xếp sửa đổi mảng, nhưng thuật toán tìm kiếm không thay đổi mảng.

Chạy qua thủ công

Hãy thử thực hiện tìm kiếm theo cách thủ công, để hiểu rõ hơn về cách hoạt động của Tìm kiếm tuyến tính trước khi thực sự triển khai nó bằng ngôn ngữ lập trình. Chúng tôi sẽ tìm kiếm giá trị 11.

Bước 1: Chúng ta bắt đầu với một mảng các giá trị ngẫu nhiên.

Bước 2: Ta xét giá trị đầu tiên trong mảng, nó có bằng 11 không?

Bước 3: Chúng ta chuyển sang giá trị tiếp theo ở chỉ số 1 và so sánh với 11 xem có bằng không.

Bước 4: Chúng ta kiểm tra giá trị tiếp theo tại chỉ số 2.

Bước 5: Chúng ta chuyển sang giá trị tiếp theo ở chỉ số 3. Nó có bằng 11 không?

Chúng tôi đã tìm thấy nó!

Giá trị 11 được tìm thấy ở chỉ số 3.

Trả về vị trí chỉ mục 3.

Tìm kiếm tuyến tính đã kết thúc.

Chạy mô phỏng bên dưới để xem các bước ở trên hoạt hình:

Chạy qua thủ công: Chuyện gì đã xảy ra?

Thuật toán này thực sự rất đơn giản.

Mọi giá trị đều được kiểm tra từ đầu mảng để xem liệu giá trị đó có bằng 11, giá trị mà chúng ta đang cố gắng tìm hay không.

Khi tìm thấy giá trị, quá trình tìm kiếm sẽ dừng lại và chỉ mục nơi tìm thấy giá trị sẽ được trả về.

Nếu tìm kiếm trong mảng mà không tìm thấy giá trị, -1 sẽ được trả về.

Triển khai tìm kiếm tuyến tính

Để thực hiện thuật toán Tìm kiếm tuyến tính, chúng ta cần:

1. Một mảng có các giá trị để tìm kiếm.
2. Một giá trị mục tiêu để tìm kiếm.
3. Một vòng lặp đi qua mảng từ đầu đến cuối.
4. Câu lệnh if so sánh giá trị hiện tại với giá trị đích và trả về chỉ mục hiện tại nếu tìm thấy giá trị đích.
5. Sau vòng lặp, trả về -1, vì tại thời điểm này chúng ta biết giá trị đích vẫn chưa được tìm thấy.

Mã kết quả cho Tìm kiếm tuyến tính trông như thế này:

 def linearSearch(arr, targetVal):
    for i in range(len(arr)):
        if arr[i] == targetVal:
            return i
    return -1

arr = [3, 7, 2, 9, 5]
targetVal = 9

result = linearSearch(arr, targetVal)

if result != -1:
    print("Value",targetVal,"found at index",result)
else:
    print("Value",targetVal,"not found")

Độ phức tạp thời gian tìm kiếm tuyến tính

Để có giải thích chung về độ phức tạp của thời gian, hãy truy cập trang này .

Để được giải thích kỹ lưỡng và chi tiết hơn về độ phức tạp về thời gian Sắp xếp chèn, hãy truy cập trang này .

Nếu Tìm kiếm tuyến tính chạy và tìm thấy giá trị đích là giá trị mảng đầu tiên trong một mảng có giá trị \(n\) thì chỉ cần một lần so sánh.

Nhưng nếu Tìm kiếm tuyến tính chạy qua toàn bộ mảng giá trị \(n\) mà không tìm thấy giá trị đích thì cần phải so sánh \(n\).

Điều này có nghĩa là độ phức tạp về thời gian của Tìm kiếm tuyến tính là

\[ TRÊN) \]

Nếu chúng ta rút ra lượng thời gian Tìm kiếm tuyến tính cần để tìm một giá trị trong một mảng các giá trị \(n\), chúng ta sẽ có được biểu đồ này:

Chạy mô phỏng bên dưới cho số lượng giá trị khác nhau trong một mảng và xem cần bao nhiêu so sánh để Tìm kiếm tuyến tính để tìm giá trị trong một mảng các giá trị \(n\):

Việc chọn "Ngẫu nhiên", "Giảm dần" hoặc "Tăng dần" trong mô phỏng ở trên không ảnh hưởng đến tốc độ Tìm kiếm tuyến tính.

 def tuyến tínhSearch(arr, targetVal):
    cho tôi trong phạm vi(len(arr)):
        nếu mảng [i] == targetVal:
          
    trở lại -1