Table Of Content

🔍 Algorithms 101: Linear Search & Binary Search – Hành Trình Tìm Kiếm!
🚀 DSA Từ A-Z: Day 2 – Binary Search Nâng Cao (Phần 2)

🔍 Algorithms 101: Linear Search & Binary Search – Hành Trình Tìm Kiếm!

Xin chào các bạn yêu quý của Loser1! Chúc mừng năm mới 2025! 🎊

Hôm nay, trong không khí Tết vui tươi và rộn ràng, chúng ta sẽ cùng nhau khám phá hai thuật toán tìm kiếm cơ bản nhưng cực kỳ quan trọng trong bộ công cụ của mọi lập trình viên. Đó chính là Linear Search và Binary Search!

Giống như việc tìm quyển sách trong thư viện, hay tìm chìa khóa trong một đống đồ, tìm kiếm là một phần không thể thiếu trong lập trình. Và hôm nay, chúng ta sẽ học cách làm điều đó một cách hiệu quả nhất!

Hãy chuẩn bị tinh thần và bắt đầu hành trình khám phá thú vị này nhé! Let’s level up our searching game! 🚀

P/S: Đừng quên cầm theo một tách trà/cà phê nóng để coding cùng Loser1 nhé! ☕

1. Linear Search – Người Đi Tìm Kho Báu 🗺️

1.1 Tư Duy Thuật Toán 🧠

Giải thích bằng ví dụ thực tế:
Hãy tưởng tượng bạn đang tìm chìa khóa trong một chùm 10 chìa. Bạn sẽ lần lượt cầm từng chìa lên và so với ổ khóa cho đến khi tìm thấy đúng chiếc. Đây chính là Linear Search!

Định nghĩa đơn giản:

Kiểm tra từng phần tử trong danh sách theo thứ tự.
Dừng lại khi tìm thấy mục tiêu hoặc duyệt hết danh sách.

1.2 Cài Đặt Thuật Toán (Implementation) 🎨

Code C++ Chi Tiết (Kèm Giải Thích Từng Dòng):

C++

int linearSearch(int arr[], int n, int x) {
    // Duyệt qua từng phần tử trong mảng
    for(int i = 0; i < n; i++) {
        // So sánh phần tử hiện tại với giá trị x cần tìm
        if(arr[i] == x) {
            return i; // Trả về vị trí nếu tìm thấy
        }
    }
    return -1;  // Trả về -1 nếu không tìm thấy
}

🔍 Visualization Step-by-Step:
Tìm x = 4 trong mảng [1, 3, 4, 7, 9]:

Bước 1: [1️⃣, 3, 4, 7, 9] → So sánh 1 và 4 → Khớp? ❌  
Bước 2: [1, 3️⃣, 4, 7, 9] → So sánh 3 và 4 → Khớp? ❌  
Bước 3: [1, 3, 4️⃣, 7, 9] → So sánh 4 và 4 → Khớp? ✅ → Trả về vị trí 2!

1.3 Các Phiên Bản Nâng Cấp 🚀

A. Sentinel Search – “Lính Gác” Thông Minh 💂

Tại sao cần? Giảm số lần so sánh trong vòng lặp.

C++

int sentinelSearch(int arr[], int n, int x) {
    int last = arr[n-1];   // Lưu lại phần tử cuối cùng
    arr[n-1] = x;          // Đặt x làm "lính gác"

    int i = 0;
    // Tìm cho đến khi gặp x (không cần check i < n)
    while(arr[i] != x) {
        i++;
    }

    arr[n-1] = last;  // Khôi phục phần tử cuối

    // Kiểm tra xem tìm thấy ở vị trí nào
    if(i < n-1 || arr[n-1] == x) {
        return i;
    } else {
        return -1;
    }
}

Ví dụ:
Tìm x = 5 trong [2, 4, 6, 8, 10] (không tồn tại):

Sau khi đặt lính gác, vòng lặp dừng ở i = 5 (ngoài mảng).
Khôi phục mảng và trả về -1.

B. Binary Linear Search – Tối Ưu Tốc Độ 🔄

Ý tưởng: Tìm từ cả hai đầu để giảm thời gian trung bình.

C++

int binaryLinearSearch(int arr[], int n, int x) {
    int left = 0, right = n-1;

    while(left <= right) {
        if(arr[left] == x) return left;   // Check đầu trái
        if(arr[right] == x) return right; // Check đầu phải
        left++;  // Thu hẹp phạm vi tìm kiếm
        right--;
    }
    return -1;
}

Ví dụ:
Tìm x = 7 trong [1, 3, 7, 9, 11]:

left = 0 (1), right = 4 (11) → Không khớp.
left = 1 (3), right = 3 (9) → Không khớp.
left = 2 (7) → Khớp! Trả về 2.

1.4 Khi Nào Dùng Linear Search?

Danh sách nhỏ (dưới 100 phần tử).
Danh sách không sắp xếp.
Cần code đơn giản, không yêu cầu tốc độ cao.

2. Binary Search – Nghệ Thuật “Chặt Nhị Phân” 🎯

2.1 Tư Duy Thuật Toán 🧠

Ví dụ kinh điển:
Bạn có một danh sách điện thoại đã sắp xếp theo tên. Để tìm “Nguyễn Văn A”, bạn sẽ:

Mở giữa danh bạ.
Nếu thấy tên bắt đầu bằng “N”, tiếp tục tìm nửa sau.
Lặp lại cho đến khi tìm thấy.

Điều kiện áp dụng:

Danh sách phải được sắp xếp (tăng dần/giảm dần).
Phần tử phải so sánh được (số, chuỗi…).

2.2 Cài Đặt Thuật Toán 🎨

Code C++ Kèm Chú Thích Từng Bước:

C++

int binarySearch(int arr[], int n, int x) {
    int left = 0, right = n-1;

    while(left <= right) {
        int mid = left + (right - left)/2;  // Tránh tràn số

        if(arr[mid] == x) {
            return mid;    // Tìm thấy tại mid
        } else if(arr[mid] < x) {
            left = mid + 1;  // Tìm nửa phải
        } else {
            right = mid - 1; // Tìm nửa trái
        }
    }
    return -1;  // Không tìm thấy
}

🔍 Visualization Chi Tiết:
Tìm x = 13 trong [2, 5, 8, 13, 13, 16, 20]:

Bước 1: left=0, right=6 → mid=3 (13) → Khớp! Trả về 3.

Tìm x = 10 trong [1, 3, 5, 7, 9, 11]:

Bước 1: [1,3,5,7,9,11] → mid=2 (5) < 10 → left=3  
Bước 2: [7,9,11] → mid=4 (9) < 10 → left=5  
Bước 3: [11] → mid=5 (11) > 10 → right=4  
→ left > right → Trả về -1.

2.3 Tips & Common Mistakes 💡

1. Tránh Tràn Số (Integer Overflow):

Vấn đề: (left + right) có thể vượt giới hạn int (2^31 – 1).
Giải pháp: Dùng mid = left + (right - left)/2.

2. Điều Kiện Vòng Lặp:

Sai: while(left < right) → Bỏ sót phần tử khi left == right.
Đúng: while(left <= right) → Xét mọi trường hợp.

3. Xử Lý Phần Tử Trùng Lặp:

Nếu có nhiều phần tử giống x, kết quả có thể là bất kỳ vị trí nào trong số chúng.
Để tìm vị trí đầu tiên/cuối cùng, cần biến thể của Binary Search (sẽ đề cập trong bài khác).

2.4 Độ Phức Tạp & So Sánh 📊

Bảng Tóm Tắt:

Thuật Toán	Thời Gian (Time)	Không Gian (Space)	Ưu Điểm	Nhược Điểm
Linear	O(n)	O(1)	Đơn giản, không cần sắp xếp	Chậm khi dữ liệu lớn
Binary	O(log n)	O(1)	Siêu nhanh với dữ liệu lớn	Cần mảng đã sắp xếp

Giải Thích O(log n) Bằng Toán Học:

Với n = 1,000,000 phần tử:
Linear Search cần ~1,000,000 bước.
Binary Search cần chỉ 20 bước (vì 2^20 ≈ 1 triệu).
Công thức: log2(n) = log10(n) / log10(2) ≈ 3.32 * log10(n).

🔥 Bài Tập Thực Hành (Kèm Đáp Án)

Bài 1:

Cho mảng [12, 23, 34, 45, 56]. Hãy mô phỏng từng bước Binary Search để tìm số 23.

Đáp án:

Bước 1: left=0, right=4 → mid=2 (34) > 23 → right=1  
Bước 2: left=0, right=1 → mid=0 (12) < 23 → left=1  
Bước 3: left=1, right=1 → mid=1 (23) → Tìm thấy!

Bài 2:

Viết hàm Binary Search đệ quy (recursive) trong C++.

Đáp án:

C++

int binarySearchRecursive(int arr[], int left, int right, int x) {
    if(left > right) return -1;

    int mid = left + (right - left)/2;

    if(arr[mid] == x) return mid;
    else if(arr[mid] < x) 
        return binarySearchRecursive(arr, mid+1, right, x);
    else 
        return binarySearchRecursive(arr, left, mid-1, x);
}

🌍 Ứng Dụng Thực Tế

Linear Search:
Tìm kiếm sản phẩm trong danh sách mua hàng (ít item).
Kiểm tra username trong database nhỏ.
Binary Search:
Tìm từ trong từ điển điện tử.
Xác định vị trí trong game map đã được sắp xếp.

🚀 DSA Từ A-Z: Day 2 – Binary Search Nâng Cao (Phần 2)

Tác giả: Loser1 từ Learning AI With Losers

🌟 3. Các Biến Thể Quan Trọng của Binary Search

Hãy tưởng tượng Binary Search như một thanh kiếm đa năng – chúng ta sẽ rèn nó thành nhiều hình dạng khác nhau!

3.1. Lower Bound & Upper Bound – Đôi Cánh Của Tìm Kiếm

🎯 Lower Bound (Cận Dưới)

Định nghĩa: Vị trí đầu tiên có giá trị ≥ x trong mảng đã sắp xếp.

Ví dụ thực tế:
Giả sử bạn muốn chèn số 5 vào mảng đã sắp xếp [2, 4, 6, 8] để duy trì thứ tự:

[2, 4, 6, 8]  
      ↑  
Chèn 5 vào vị trí 2 (vị trí đầu tiên ≥5)

Code C++ với giải thích từng dòng:

C++

int lowerBound(vector<int>& arr, int x) {
    int left = 0;
    int right = arr.size(); // 🚩 Right ban đầu = n (không phải n-1)

    while (left < right) {  // 🔄 Dừng khi left == right
        int mid = left + (right - left)/2; // ⚠️ Tránh tràn số

        if (arr[mid] < x) {
            left = mid + 1; // ➡️ Dịch sang phải
        } else {
            right = mid;    // ⬅️ Giữ nguyên right (mid có thể là kết quả)
        }
    }

    return left; // 🏁 Kết quả cuối cùng
}

🔍 Visualization:
Tìm lower_bound(5) trong [2, 4, 5, 5, 7]:

Step 1: [2,4,5,5,7] → mid=2 (5) → right=2  
Step 2: [2,4] → mid=1 (4 <5) → left=2  
→ left == right → return 2 (vị trí đầu tiên của 5)

🎯 Upper Bound (Cận Trên)

Định nghĩa: Vị trí đầu tiên có giá trị > x trong mảng đã sắp xếp.

Ví dụ thực tế:
Trong mảng [1, 3, 3, 5, 7], upper_bound(3) là vị trí 3 (phần tử 5).

Code C++:

C++

int upperBound(vector<int>& arr, int x) {
    int left = 0;
    int right = arr.size();

    while (left < right) {
        int mid = left + (right - left)/2;

        if (arr[mid] <= x) {
            left = mid + 1; // ➡️ Bỏ qua nửa trái
        } else {
            right = mid;    // ⬅️ Giữ right
        }
    }

    return left; 
}

📌 Bảng So Sánh:

Thuật Toán	Mục Đích	Ví dụ (x=5) trong [2,5,5,7]
Lower Bound	Tìm vị trí đầu ≥x	Trả về 1
Upper Bound	Tìm vị trí đầu >x	Trả về 3

3.2. Ứng Dụng: Đếm Số Lần Xuất Hiện

Công thức thần thánh:
Số lần xuất hiện = UpperBound(x) - LowerBound(x)

Code Demo:

C++

int countOccurrences(vector<int>& arr, int x) {
    int first = lowerBound(arr, x);
    int last = upperBound(arr, x);

    // 🚨 Kiểm tra xem x có tồn tại không
    if (first == arr.size() || arr[first] != x) return 0;

    return last - first;
}

Ví dụ Trực Quan:

Mảng: [1, 2, 2, 2, 3, 4]  
LowerBound(2) = 1  
UpperBound(2) = 4  
→ Số lần xuất hiện: 4 -1 = 3 ✨

[2, 4, 5, 5, 7, 9]  
     ↑        ↑  
LB(5)=2   UB(5)=4

🌌 4. Binary Search Trên Dãy Không Đơn Điệu

4.1. Tìm Đỉnh Cục Bộ (Peak Element)

Định nghĩa: Phần tử lớn hơn các phần tử lân cận.

Ví dụ Thực Tế:
Tưởng tượng bạn đang leo núi – đỉnh núi là điểm cao nhất so với xung quanh.

Code Tìm Peak:

C++

int findPeak(vector<int>& arr) {
    int left = 0, right = arr.size()-1;

    while (left < right) {
        int mid = left + (right - left)/2;

        if (arr[mid] < arr[mid+1]) { 
            left = mid + 1; // ↗️ Đang lên dốc → peak bên phải
        } else {
            right = mid;    // ↖️ Đang xuống dốc → peak bên trái
        }
    }
    return left; 
}

🔍 Visualization:
Mảng: [1, 3, 20, 4, 1]

Step 1: mid=2 (20) → 20 >4 → right=2  
Step 2: left=0, right=2 → mid=1 (3 <20) → left=2  
→ Kết quả: 2 (phần tử 20)

4.2. Tìm Kiếm Trong Mảng Xoay

Ví dụ Mảng Xoay:
[4,5,6,7,0,1,2] (mảng gốc [0,1,2,4,5,6,7] xoay tại index 3)

Code Giải Thuật:

C++

int searchRotated(vector<int>& arr, int target) {
    int left = 0, right = arr.size()-1;

    while (left <= right) {
        int mid = left + (right - left)/2;

        if (arr[mid] == target) return mid;

        // Xác định nửa nào được sắp xếp
        if (arr[left] <= arr[mid]) { // Nửa trái sorted
            if (arr[left] <= target && target < arr[mid]) {
                right = mid -1; // Tìm bên trái
            } else {
                left = mid +1; // Chuyển sang nửa phải
            }
        } else { // Nửa phải sorted
            if (arr[mid] < target && target <= arr[right]) {
                left = mid +1; // Tìm bên phải
            } else {
                right = mid -1;
            }
        }
    }
    return -1;
}

📝 Giải Thích Bằng Hình:

Mảng: [4,5,6,7,0,1,2], target=0  
Step 1: mid=3 (7) → nửa trái [4,5,6,7] sorted → 0 không thuộc → chuyển phải  
Step 2: mid=5 (1) → nửa phải [0,1,2] sorted → 0 nằm ở left  
→ Tìm thấy tại index 4

🛠️ 5. Binary Search Cho Bài Toán Tối Ưu

Original: [0,1,2,4,5,6,7]  
Rotated:  [4,5,6,7,0,1,2]  
          ↖️ Phần sorted → [4,5,6,7]  
                     ↘️ Phần sorted → [0,1,2]

5.1. Tính Căn Bậc Hai

Ý Tưởng: Coi căn bậc hai là “điểm chia” giữa các số có bình phương ≤x và >x.

Code Tính Căn:

C++

double sqrt(double x, double eps=1e-10) {
    double left = 0, right = max(1.0, x);

    while (right - left > eps) {
        double mid = (left + right)/2;
        if (mid*mid > x) {
            right = mid; // ⬇️ Giảm upper bound
        } else {
            left = mid;  // ⬆️ Tăng lower bound
        }
    }
    return left;
}

📌 Ví dụ:
Tính sqrt(2):

Lặp 1: left=0, right=2 → mid=1 (1 <2) → left=1  
Lặp 2: left=1, right=2 → mid=1.5 (2.25 >2) → right=1.5  
...  
Kết quả ≈1.41421356237

5.2. Tìm Giá Trị Nhỏ Nhất Thỏa Mãn

Pattern Chung:

Tìm số k nhỏ nhất sao cho hàm f(k) ≥ target

Code Mẫu:

C++

int findMinValid(function<bool(int)> f, int target) {
    int left = 0, right = 1;

    // 🚀 Tìm right đủ lớn
    while (!f(right)) right *= 2;

    // Binary Search
    while (left < right) {
        int mid = left + (right - left)/2;
        if (f(mid)) {
            right = mid; // ✅ Tìm giá trị nhỏ hơn
        } else {
            left = mid +1; // ❌ Bỏ qua nửa trái
        }
    }
    return left;
}

Ví dụ Ứng Dụng:
Tìm số ngày nhỏ nhất để đạt doanh thu 1000$, biết doanh thu tăng theo cấp số nhân.

💡 Tips Pro Từ Loser1

Luôn Kiểm Tra Edge Cases:

Mảng rỗng
Tất cả phần tử bằng x
Target nằm ngoài mảng

Vẽ Ra Giấy Khi Debug:

Vẽ mảng và các chỉ số left/right/mid
Theo dõi sự thay đổi qua từng vòng lặp

Thực Hành Trên LeetCode:

Bài tập đề xuất: #34 (Find First and Last Position), #162 (Find Peak Element), #33 (Search in Rotated Sorted Array)

“Học Binary Search như tập võ – càng luyện nhiều càng thấm sâu! “ 💪🚀

Tiếp tục học DSA cùng Losers

📚 Đọc Phần Tiếp Theo: Bài Tập Search

P/S: Follow mình tại Learning AI with Loser để cập nhật các bài DSA thú vị khác nhé! 💻✨

#dsa #algorithms #programming #learningwithlosers