Tìm kiếm tuyến tính trong Python: Hướng dẫn cho người mới bắt đầu kèm ví dụ

Khi nói đến các thuật toán tìm kiếm, tìm kiếm tuyến tính là một trong những thuật toán đơn giản nhất. Nếu bạn từng lần lượt xem qua một danh sách cho đến khi tìm được thứ mình cần, thì bạn đã thực hiện tìm kiếm tuyến tính rồi!

Bên cạnh việc dễ hiểu, tìm kiếm tuyến tính còn hữu ích vì nó hoạt động trên dữ liệu chưa sắp xếp, khác với một số thuật toán tìm kiếm khác. Tính linh hoạt này khiến nó hữu dụng trong những tình huống không thể sắp xếp dữ liệu. Tôi sẽ dùng Python trong hướng dẫn này, nên nếu bạn muốn ôn lại Python trước khi bắt đầu, hãy xem lộ trình kỹ năng Python Programming.

Tìm kiếm tuyến tính là gì?

Tìm kiếm tuyến tính là thuật toán xác định vị trí một giá trị cụ thể trong danh sách bằng cách kiểm tra từng phần tử một. Nó bắt đầu ở phần tử đầu tiên, so sánh với mục tiêu, rồi tiếp tục đi qua danh sách cho đến khi tìm thấy mục tiêu hoặc đến cuối danh sách. Đây là một thuật toán đơn giản và trực quan.

Tìm kiếm tuyến tính không cần dữ liệu phải được sắp xếp để hoạt động, vì vậy chủ yếu được dùng với tập dữ liệu chưa sắp xếp. Điều này hữu ích khi việc sắp xếp không thực tế, hoặc bạn làm việc với dữ liệu thô. Tuy nhiên, lợi ích này đi kèm chi phí: nó kém hiệu quả hơn so với các thuật toán yêu cầu dữ liệu đã sắp xếp trước.

Tìm kiếm tuyến tính lý tưởng khi bạn làm việc với các tập dữ liệu tương đối nhỏ hoặc khi không thể sắp xếp dữ liệu. Sơ đồ dưới đây đưa ra một giải thích đơn giản.

Khi nào chọn tìm kiếm tuyến tính

Hãy xem các ưu điểm và một nhược điểm rõ rệt:

Vì sao chọn tìm kiếm tuyến tính?

Theo tôi, tìm kiếm tuyến tính có ba lợi ích nổi bật:

Khi sự đơn giản là then chốt

Một trong những ưu điểm lớn nhất của tìm kiếm tuyến tính là tính đơn giản. Thuật toán này dễ hiểu và dễ triển khai. Không cần bận tâm đến việc sắp xếp hay chia nhỏ dữ liệu phức tạp. Chỉ cần bắt đầu từ đầu danh sách và kiểm tra từng phần tử cho đến khi bạn tìm thấy thứ mình cần.

Khi bạn không có thời gian để sắp xếp

Không giống các thuật toán khác như tìm kiếm nhị phân, tìm kiếm tuyến tính không yêu cầu tập dữ liệu phải được sắp xếp. Điều này lý tưởng khi bạn cần tìm nhanh một thứ gì đó.

Khi bạn cần tính linh hoạt

Một điểm cộng khác của tìm kiếm tuyến tính là tính linh hoạt. Nó không chỉ hoạt động với mảng mà còn với các cấu trúc dữ liệu khác của Python, như danh sách liên kết. Miễn là bạn có thể truy cập tuần tự các phần tử, tìm kiếm tuyến tính có thể hoàn thành nhiệm vụ. Nó đủ linh hoạt để xử lý nhiều kiểu dữ liệu, từ số, chuỗi đến đối tượng.

Vì sao nên cân nhắc trước khi dùng tìm kiếm tuyến tính?

Có một vấn đề cần lưu ý:

Khi hiệu suất quan trọng

Nhược điểm lớn nhất của tìm kiếm tuyến tính là kém hiệu quả, đặc biệt với tập dữ liệu lớn. Độ phức tạp thời gian là O(n), nghĩa là trong trường hợp xấu nhất, bạn có thể phải kiểm tra mọi phần tử trong danh sách! Điều này có thể làm chậm đáng kể khi bạn làm việc với hàng nghìn hoặc hàng triệu bản ghi. Tuy nhiên, với tập dữ liệu nhỏ, sự kém hiệu quả này có thể không đáng kể.

Cài đặt thuật toán tìm kiếm tuyến tính trong Python

Trong Python, có hai cách phổ biến để viết tìm kiếm tuyến tính: phương pháp lặp và phương pháp đệ quy. Để minh họa, trước tiên hãy tạo một tập dữ liệu đơn giản gồm 100 số không trùng nhau.

numbers = [12, 7, 19, 3, 15, 25, 8, 10, 42, 56, 77, 23, 89, 65, 33, 99, 14, 2, 37, 81,
           48, 64, 22, 91, 6, 40, 59, 87, 28, 53, 74, 9, 16, 39, 71, 93, 54, 32, 61, 27,
           35, 18, 49, 68, 83, 46, 57, 29, 95, 11, 26, 44, 78, 5, 66, 73, 41, 85, 31, 50,
           20, 63, 88, 34, 90, 60, 67, 4, 52, 36, 62, 80, 21, 84, 98, 13, 45, 69, 30, 38,
           47, 17, 92, 55, 70, 76, 82, 24, 43, 1, 100, 58, 96, 75, 97, 94, 86, 72, 51, 79]Được hỗ trợ bởi

Phương pháp lặp

Cách tiếp cận lặp có lẽ là cách dễ hiểu nhất về tìm kiếm tuyến tính. Bạn lặp qua danh sách, kiểm tra từng phần tử cho đến khi tìm thấy mục tiêu hoặc đến cuối.

Đầu tiên, chúng ta sẽ tạo hàm:

1. Chúng ta sẽ lặp qua từng phần tử trong danh sách arr.

2. So sánh từng phần tử với mục tiêu.

3. Nếu khớp, trả về chỉ số nơi tìm thấy mục tiêu.

4. Nếu kết thúc vòng lặp mà không thấy mục tiêu, trả về 1 để cho biết phần tử không tồn tại.

def linear_search_iterative(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return the index if the target is found
    return -1  # Return -1 if the target is not foundĐược hỗ trợ bởi

Tiếp theo, chúng ta chạy hàm với tập dữ liệu và in kết quả:

# Run the function on the numbers list
target = 91
index = linear_search_iterative(numbers, target)

if index != -1:
    print(f"Target {target} found at index {index}")
else:
    print(f"Target {target} not found!")Được hỗ trợ bởi

Chạy đoạn mã này, chúng ta tìm thấy giá trị mục tiêu ở phần tử thứ 23.

Phương pháp đệ quy

Phương pháp đệ quy dùng một hàm tự gọi chính nó để tìm kiếm qua danh sách. Mỗi lần gọi đệ quy xử lý một phần tử, rồi chuyển sang phần tử tiếp theo. Tiến trình tiếp tục cho đến khi tìm thấy mục tiêu hoặc đến cuối danh sách.

Hãy tạo hàm đệ quy:

1. Bắt đầu bằng cách kiểm tra phần tử đầu tiên (ở chỉ số 0).
2. Nếu khớp với mục tiêu, trả về chỉ số.
3. Nếu không khớp, gọi lại chính hàm đó theo kiểu đệ quy, nhưng tăng chỉ số thêm 1 để kiểm tra phần tử tiếp theo.
4. Tiếp tục đệ quy cho đến khi tìm thấy mục tiêu hoặc đến cuối danh sách.

def linear_search_recursive(arr, target, index=0):
    if index >= len(arr):  # Base case: we've checked all elements
        return -1
    if arr[index] == target:  # Base case: target found
        return index
    return linear_search_recursive(arr, target, index + 1)  # Recursive case: check next elementĐược hỗ trợ bởi

Chúng ta có thể dùng cùng đoạn mã ở trên để chạy hàm này và nó trả về cùng chỉ số cho mục tiêu: 23.

Lưu ý rằng cách tiếp cận này dùng nhiều bộ nhớ hơn vì mỗi lần gọi đệ quy sẽ thêm một lớp vào ngăn xếp lệnh gọi. Xem thêm Understanding Recursive Functions in Python để tìm hiểu kỹ hơn về đệ quy.

Độ phức tạp thời gian và không gian

Một cách để đánh giá hiệu quả của thuật toán là xem độ phức tạp thời gian và không gian. Hãy xem hướng dẫn Analyzing Complexity of Code through Python để biết các cách đo độ phức tạp của thuật toán.

Độ phức tạp thời gian

Độ phức tạp thời gian đề cập đến việc thời gian thực thi tăng như thế nào khi kích thước đầu vào tăng. Độ phức tạp thời gian của tìm kiếm tuyến tính là O(n), với n là số phần tử trong danh sách. Nghĩa là trong trường hợp xấu nhất, thuật toán có thể phải kiểm tra mọi phần tử trước khi tìm thấy mục tiêu (hoặc xác định rằng mục tiêu không có trong danh sách). Điều này khá kém hiệu quả, đặc biệt đối với tập dữ liệu lớn. Vì vậy, tìm kiếm tuyến tính hoạt động tốt nhất khi chúng ta có các tập dữ liệu nhỏ, chưa sắp xếp và chỉ cần tìm kiếm một lần.

Độ phức tạp không gian

Độ phức tạp không gian đo lượng bộ nhớ cần thiết khi kích thước đầu vào tăng. Độ phức tạp không gian của thuật toán tìm kiếm tuyến tính phụ thuộc vào phương pháp sử dụng. Với phương pháp lặp, độ phức tạp không gian là O(1), nghĩa là thuật toán cần một lượng bộ nhớ hằng số, bất kể kích thước danh sách đầu vào. Bởi vì phiên bản lặp không yêu cầu thêm bộ nhớ, ngoài danh sách đầu vào và một vài biến để theo dõi chỉ số hiện tại.

Với phương pháp đệ quy, độ phức tạp không gian là O(n), tức là bộ nhớ cần thiết tăng tuyến tính theo kích thước danh sách đầu vào. Nguyên nhân là các lời gọi hàm đệ quy, mỗi phần tử trong danh sách sẽ thêm một lớp vào ngăn xếp lệnh gọi. Danh sách càng lớn càng cần nhiều bộ nhớ để lưu các lời gọi đó, khiến cách tiếp cận đệ quy kém hiệu quả về không gian hơn.

Ứng dụng thực tế của tìm kiếm tuyến tính

Dù có thể không phải là thuật toán hiệu quả nhất cho tập dữ liệu lớn, tìm kiếm tuyến tính vẫn có nhiều ứng dụng thực tế. Hãy xem một số tình huống mà tìm kiếm tuyến tính là công cụ phù hợp nhất.

Tập dữ liệu nhỏ, khó sắp xếp

Tìm kiếm tuyến tính thường là lựa chọn của tôi khi xử lý tập dữ liệu nhỏ, không đáng để tốn thời gian hoặc tài nguyên để sắp xếp. Trong những trường hợp này, sự đơn giản của tìm kiếm tuyến tính có thể hiệu quả hơn chi phí phụ trội của việc sắp xếp dữ liệu để dùng các thuật toán tìm kiếm phức tạp hơn.

Tìm lần xuất hiện đầu tiên của mục tiêu

Một trường hợp sử dụng phổ biến khác là khi bạn cần tìm lần xuất hiện đầu tiên của một giá trị mục tiêu. Vì tìm kiếm tuyến tính duyệt qua danh sách từng phần tử một, nó tự nhiên sẽ tìm thấy lần xuất hiện đầu tiên và trả về vị trí của nó. Điều này đặc biệt hữu ích, chẳng hạn như khi tìm ký tự xuất hiện đầu tiên trong một chuỗi.

Khi cần thiết lập tối thiểu

Đôi khi, sự đơn giản của tìm kiếm tuyến tính khiến nó trở thành lựa chọn tốt nhất. Ví dụ, nếu bạn cần tìm nhanh trong dữ liệu mà bạn không định dùng lại, hoặc cần một con số ước lượng nhanh, việc thiết lập tối thiểu của tìm kiếm tuyến tính có thể giúp tiết kiệm thời gian.

Tìm kiếm tuyến tính so với các thuật toán khác

Tìm kiếm tuyến tính chỉ là một trong nhiều thuật toán tìm kiếm. Hãy xem hai thuật toán phổ biến khác: tìm kiếm nhị phân và tra cứu băm.

Tìm kiếm tuyến tính vs. tìm kiếm nhị phân

Tìm kiếm nhị phân là thuật toán tìm vị trí của giá trị mục tiêu trong một mảng đã sắp xếp bằng cách lặp lại việc chia đôi khoảng tìm kiếm. Nó có độ phức tạp thời gian O(log n), hiệu quả hơn nhiều so với tìm kiếm tuyến tính. Tuy nhiên, nó chỉ hoạt động trên dữ liệu đã sắp xếp. Khi tập dữ liệu đã sắp xếp, tìm kiếm nhị phân hầu như luôn là lựa chọn tốt hơn vì mỗi bước cắt giảm một nửa không gian tìm kiếm, giảm mạnh số lần so sánh cần thiết để tìm mục tiêu.

Tìm kiếm tuyến tính có thể phù hợp hơn khi dữ liệu của bạn chưa sắp xếp, vì nó hoạt động với mọi tập dữ liệu, bất kể đã sắp xếp hay chưa. Tuy nhiên, với độ phức tạp O(n), tìm kiếm tuyến tính kém hiệu quả hơn nhiều trên các tập dữ liệu đã sắp xếp.

Tìm kiếm tuyến tính vs. tra cứu băm

Tra cứu băm sử dụng bảng băm để tìm phần tử nhanh chóng. Với độ phức tạp thời gian O(1), nó nhanh hơn đáng kể so với cả tìm kiếm tuyến tính lẫn nhị phân. Tuy nhiên, tốc độ này có cái giá: bạn cần xây dựng bảng băm trước, tốn thời gian và bộ nhớ bổ sung. Tra cứu băm phù hợp nhất khi bạn cần tìm kiếm nhiều lần trên tập dữ liệu lớn để chi phí thiết lập ban đầu được bù đắp theo thời gian.

Ngược lại, tìm kiếm tuyến tính không cần thiết lập, nên đơn giản hơn. Nó là lựa chọn tốt hơn khi bạn chỉ cần tìm kiếm một hoặc vài lần, nơi việc bỏ thêm thời gian để thiết lập bảng băm là không đáng. Tìm kiếm tuyến tính cũng có thể tiết kiệm không gian hơn vì bạn không cần lưu bảng băm để dùng thuật toán.

Lỗi thường gặp và cách tránh

Mặc dù là một thuật toán đơn giản, tìm kiếm tuyến tính vẫn có vài lỗi thường gặp cần chú ý.

Lỗi lệch một đơn vị khi lặp

Một lỗi thường gặp là lệch một đơn vị, do bắt đầu hoặc kết thúc vòng lặp ở chỉ số sai. Cần nhớ rằng danh sách trong Python đánh chỉ số từ 0, nghĩa là phần tử đầu tiên có chỉ số 0. Quên điều này có thể khiến bạn vô tình bỏ qua phần tử đầu tiên hoặc lặp quá một bước, dẫn đến kết quả sai hoặc lỗi.

Hiểu nhầm chỉ số trả về

Một lỗi khác là hiểu nhầm giá trị hàm trả về khi không tìm thấy mục tiêu trong danh sách. Theo quy ước, nhiều thuật toán tìm kiếm (bao gồm tìm kiếm tuyến tính) trả về -1 để chỉ ra rằng mục tiêu không tồn tại. Tuy nhiên, một số người mới có thể cho rằng nó trả về None, False, hoặc giá trị khác, dẫn đến nhầm lẫn khi diễn giải kết quả.

Khi không nên dùng tìm kiếm tuyến tính

Như đã đề cập, tìm kiếm tuyến tính nhanh chóng trở nên kém hiệu quả với tập dữ liệu lớn. Vì vậy, tốt nhất hãy dành nó cho các tập dữ liệu nhỏ, chưa sắp xếp hoặc các tìm kiếm nhanh, một lần.

Kết luận

Là một trong những phương pháp tìm kiếm đơn giản nhất, tìm kiếm tuyến tính kiểm tra tuần tự từng phần tử trong danh sách, nên dễ hiểu và dễ triển khai. Đây là lựa chọn đáng tin cậy cho các tìm kiếm nhanh, một lần trên tập dữ liệu nhỏ, đặc biệt khi dữ liệu chưa sắp xếp.

Nếu bạn quan tâm đến các thuật toán tìm kiếm, hãy xem các bài khác trong chuỗi của tôi: Tìm kiếm nhị phân trong Python, Tìm kiếm theo chiều sâu trong Python, và Tìm kiếm theo chiều rộng trong Python. Bạn cũng có thể quan tâm đến AVL Tree: Complete Guide With Python Implementation và Introduction to Network Analysis in Python như những chủ đề nâng cao hơn.