Viết chương trình Linear Search (Tìm kiếm tuyến tính) trong Python

Linear Search (tìm kiếm tuyến tính) là kỹ thuật tìm kiếm một giá trị cụ thể từ mảng. Đây là kỹ thuật tìm kiếm đơn giản nhất.

Trong kỹ thuật này:

• Giá trị cần tìm so sánh với tất cả phần tử trong mảng.
• Nếu tìm thấy, trả về chỉ số của phần tử.
• Nếu phần tử không có trong mảng, trả về -1 hoặc thông báo liên quan.

Pseudocode

linearSearch(int array[], int value):
    for i = 0 to len(array):
        if array[i] == value:
            Element is Present
    // outside for loop
    Element Not Present // element not found in whole array

Ví dụ

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

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
value = 5
a = linearSearch(array, value)
if a == -1:
    print("Phần tử không có mặt")
else:
    print("Phần tử có mặt tại chỉ số", a)

Kết quả

Phần tử có mặt tại chỉ số 4

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

Độ phức tạp thời gian trường hợp xấu nhất của linear search là O(n). Trường hợp xấu xảy ra khi phần tử ở chỉ số cuối hoặc không có.

Độ phức tạp thời gian trường hợp tốt nhất là O(1). Xảy ra khi phần tử ở chỉ số đầu tiên.

Linear Search cải tiến

Độ phức tạp xấu nhất có thể cải tiến thành O(n/2). Làm bằng cách dùng hai con trỏ left và right và thực hiện hai so sánh cùng lúc, giảm độ phức tạp xấu nhất xuống O(n/2).

Ví dụ

def linearSearch(arr, value):
    left = 0
    right = len(arr) - 1
    while left <= right:
        if arr[left] == value:
            return left
        elif arr[right] == value:
            return right
        left += 1
        right -= 1
    return -1

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
value = 10
a = linearSearch(array, value)
if a == -1:
    print("Phần tử không có mặt")
else:
    print("Phần tử có mặt tại chỉ số", a)

Kết quả

Phần tử có mặt tại chỉ số 9

Trong ví dụ trên, phần tử ở chỉ số cuối được tìm thấy ngay lần lặp đầu. Dùng phương pháp đầu sẽ mất 10 lần lặp.

Nếu không tìm thấy, độ phức tạp xấu nhất là O(n/2), vì tổng số lần lặp là n/2 trong phương pháp 2.

Linear Search có hữu ích không?

Linear search hiếm khi dùng vì có thuật toán tốt hơn như binary search với độ phức tạp thời gian tốt hơn. Linear search không hiệu quả cho mảng đầu vào lớn.