08. Searching Algorithms (Thuật toán tìm kiếm)

🎯 Mục tiêu học tập

  • Hiểu các thuật toán tìm kiếm cơ bản
  • So sánh Linear vs Binary Search
  • Cài đặt các biến thể của Binary Search
  • Áp dụng vào bài toán thực tế

📊 Tổng quan

Thuật toán Time Complexity Space Điều kiện
Linear Search O(n) O(1) Không
Binary Search O(log n) O(1) Array đã sorted
Exponential Search O(log n) O(1) Array đã sorted
Interpolation Search O(log log n) O(1) Uniformly distributed

Ý tưởng: Duyệt tuần tự từ đầu đến cuối

for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) return i;
}
return -1;
  • Ưu điểm: Đơn giản, không cần array sorted
  • Nhược điểm: Chậm O(n)

Ý tưởng: Chia đôi không gian tìm kiếm

while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}
  • Điều kiện: Array phải sorted
  • Time: O(log n)

🎨 Binary Search Variants

1. First Occurrence

// Tìm vị trí đầu tiên của target
// Khi tìm thấy, tiếp tục tìm bên trái

2. Last Occurrence

// Tìm vị trí cuối cùng của target
// Khi tìm thấy, tiếp tục tìm bên phải

3. Lower Bound

// Tìm vị trí đầu tiên >= target

4. Upper Bound

// Tìm vị trí đầu tiên > target
  • Tìm range [0, 2^i] chứa target
  • Sau đó binary search trong range
  • Guess vị trí dựa trên value
  • Phù hợp với data uniformly distributed
  • Chia thành 3 phần thay vì 2
  • Dùng cho unimodal functions

📋 Bài tập thực hành

Cơ bản:

  1. Linear và Binary Search
  2. First/Last occurrence
  3. Search in rotated sorted array
  4. Find peak element

Nâng cao:

  1. Search in 2D matrix
  2. Find minimum in rotated sorted array
  3. Search for range
  4. Median of two sorted arrays

🚀 Chuẩn bị code

mkdir 08-searching
# Files: LinearSearch.java, BinarySearch.java, SearchVariants.java, SearchProblems.java