Tìm kiếm tuyến tính (Linear Search): từ cơ bản đến kỹ thuật lính canh và code C++, Python

#include <iostream>
#include <vector>
using namespace std;

// 1. Tìm vị trí xuất hiện đầu tiên của x (trả về -1 nếu không có)
int tim_vi_tri_dau(const vector<int>& a, int x) {
    for (int i = 0; i < (int)a.size(); ++i) {
        if (a[i] == x) {
            return i;
        }
    }
    return -1;
}

// 2. Tìm vị trí xuất hiện cuối cùng của x (duyệt ngược từ cuối về đầu)
int tim_vi_tri_cuoi(const vector<int>& a, int x) {
    for (int i = (int)a.size() - 1; i >= 0; --i) {
        if (a[i] == x) {
            return i;
        }
    }
    return -1;
}

// 3. Kỹ thuật lính canh (Sentinel Linear Search): bỏ kiểm tra i < n trong vòng lặp
int tim_linh_canh(vector<int> a, int x) {
    int n = (int)a.size();
    a.push_back(x); // Đặt lính canh x ở vị trí a[n]
    int i = 0;
    while (a[i] != x) {
        ++i; // Chắc chắn dừng vì có lính canh ở cuối
    }
    return (i < n) ? i : -1;
}

int main() {
    vector<int> a = {14, 7, 25, 7, 9, 30};

    // Test 1: Phần tử 7 xuất hiện nhiều lần (đầu tiên ở 1, cuối cùng ở 3)
    cout << "Dau(7): " << tim_vi_tri_dau(a, 7)
         << " | Cuoi(7): " << tim_vi_tri_cuoi(a, 7)
         << " | LinhCanh(7): " << tim_linh_canh(a, 7) << "\n";

    // Test 2: Phần tử 30 nằm ở cuối mảng (chỉ số 5)
    cout << "Dau(30): " << tim_vi_tri_dau(a, 30)
         << " | Cuoi(30): " << tim_vi_tri_cuoi(a, 30)
         << " | LinhCanh(30): " << tim_linh_canh(a, 30) << "\n";

    // Test 3: Phần tử 99 không tồn tại trong mảng (trả về -1)
    cout << "Dau(99): " << tim_vi_tri_dau(a, 99)
         << " | Cuoi(99): " << tim_vi_tri_cuoi(a, 99)
         << " | LinhCanh(99): " << tim_linh_canh(a, 99) << "\n";

    return 0;
}

def tim_vi_tri_dau(a: list[int], x: int) -> int:
    """1. Tìm vị trí xuất hiện đầu tiên của x (trả về -1 nếu không có)."""
    for i, val in enumerate(a):
        if val == x:
            return i
    return -1


def tim_vi_tri_cuoi(a: list[int], x: int) -> int:
    """2. Tìm vị trí xuất hiện cuối cùng của x (duyệt ngược từ cuối về đầu)."""
    for i in range(len(a) - 1, -1, -1):
        if a[i] == x:
            return i
    return -1


def tim_linh_canh(mang_goc: list[int], x: int) -> int:
    """3. Kỹ thuật lính canh (Sentinel Linear Search): bỏ kiểm tra i < n trong vòng lặp."""
    a = mang_goc[:]
    n = len(a)
    a.append(x)  # Đặt lính canh x ở vị trí a[n]
    i = 0
    while a[i] != x:
        i += 1  # Chắc chắn dừng vì có lính canh ở cuối
    return i if i < n else -1


if __name__ == "__main__":
    a = [14, 7, 25, 7, 9, 30]

    # Test 1: Phần tử 7 xuất hiện nhiều lần (đầu tiên ở 1, cuối cùng ở 3)
    print(
        f"Dau(7): {tim_vi_tri_dau(a, 7)} | "
        f"Cuoi(7): {tim_vi_tri_cuoi(a, 7)} | "
        f"LinhCanh(7): {tim_linh_canh(a, 7)}"
    )

    # Test 2: Phần tử 30 nằm ở cuối mảng (chỉ số 5)
    print(
        f"Dau(30): {tim_vi_tri_dau(a, 30)} | "
        f"Cuoi(30): {tim_vi_tri_cuoi(a, 30)} | "
        f"LinhCanh(30): {tim_linh_canh(a, 30)}"
    )

    # Test 3: Phần tử 99 không tồn tại trong mảng (trả về -1)
    print(
        f"Dau(99): {tim_vi_tri_dau(a, 99)} | "
        f"Cuoi(99): {tim_vi_tri_cuoi(a, 99)} | "
        f"LinhCanh(99): {tim_linh_canh(a, 99)}"
    )

#include <climits>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

// Tìm giá trị lớn nhất (max1) và lớn thứ hai phân biệt (max2) chỉ trong 1 vòng duyệt
// Nếu không tồn tại max2 phân biệt, max2 giữ giá trị LLONG_MIN
pair<long long, long long> tim_hai_so_lon_nhat(const vector<long long>& a) {
    long long max1 = LLONG_MIN;
    long long max2 = LLONG_MIN;
    for (long long val : a) {
        if (val > max1) {
            max2 = max1; // Cựu vô địch lùi xuống làm á quân
            max1 = val;  // Tân vô địch mới
        } else if (val < max1 && val > max2) {
            max2 = val;  // Nhỏ hơn max1 nhưng vượt qua max2 hiện tại
        }
    }
    return {max1, max2};
}

void in_ket_qua(const vector<long long>& a) {
    auto [max1, max2] = tim_hai_so_lon_nhat(a);
    cout << "max1: " << max1 << " | max2: ";
    if (max2 == LLONG_MIN) cout << "NONE\n";
    else cout << max2 << "\n";
}

int main() {
    // Test 1: Mảng có giá trị lớn nhất lặp lại nhiều lần
    in_ket_qua({12, 35, 1, 10, 35, 34}); // max1: 35 | max2: 34

    // Test 2: Mảng số âm
    in_ket_qua({-10, -3, -25, -7});      // max1: -3 | max2: -7

    // Test 3: Mọi phần tử bằng nhau -> không có giá trị lớn thứ hai phân biệt
    in_ket_qua({8, 8, 8});               // max1: 8 | max2: NONE

    return 0;
}

def tim_hai_so_lon_nhat(a: list[int]) -> tuple[int | None, int | None]:
    """Tìm giá trị lớn nhất (max1) và lớn thứ hai phân biệt (max2) chỉ trong 1 vòng duyệt."""
    max1: int | None = None
    max2: int | None = None
    for val in a:
        if max1 is None or val > max1:
            max2 = max1  # Cựu vô địch lùi xuống làm á quân
            max1 = val   # Tân vô địch mới
        elif val < max1 and (max2 is None or val > max2):
            max2 = val   # Nhỏ hơn max1 nhưng vượt qua max2 hiện tại
    return max1, max2


def in_ket_qua(a: list[int]) -> None:
    max1, max2 = tim_hai_so_lon_nhat(a)
    print(f"max1: {max1} | max2: {'NONE' if max2 is None else max2}")


if __name__ == "__main__":
    # Test 1: Mảng có giá trị lớn nhất lặp lại nhiều lần
    in_ket_qua([12, 35, 1, 10, 35, 34])  # max1: 35 | max2: 34

    # Test 2: Mảng số âm
    in_ket_qua([-10, -3, -25, -7])       # max1: -3 | max2: -7

    # Test 3: Mọi phần tử bằng nhau -> không có giá trị lớn thứ hai phân biệt
    in_ket_qua([8, 8, 8])                # max1: 8 | max2: NONE