Khóa học CTDL và GT

Bài 16.5: Bài tập tổng hợp về Binary Search

Chào mừng quay trở lại với series blog về Cấu trúc dữ liệu và Giải thuật! Trong bài trước, chúng ta đã tìm hiểu về Thuật toán Tìm kiếm Nhị phân (Binary Search) - một thuật toán cực kỳ hiệu quả để tìm kiếm một phần tử trong một mảng đã được sắp xếp. Độ phức tạp thời gian của Binary Search là O(log n), vượt trội hơn hẳn so với tìm kiếm tuyến tính O(n) khi làm việc với các tập dữ liệu lớn.

Học lý thuyết là một chuyện, nhưng để thực sự thành thạo Binary Search và biết cách áp dụng nó vào giải quyết các bài toán khác nhau, việc thực hành qua các bài tập là cực kỳ quan trọng. Binary Search có nhiều biến thể khác nhau, và hiểu được cách điều chỉnh thuật toán cơ bản để phù hợp với yêu cầu cụ thể của bài toán là chìa khóa thành công.

Bài viết này sẽ tổng hợp một số dạng bài tập phổ biến về Binary Search, đi kèm với code minh họa bằng C++ và giải thích chi tiết. Hãy cùng bắt tay vào thực hành nhé!

Bài tập 1: Tìm kiếm Cơ bản

Đây là dạng bài tập kinh điển nhất của Binary Search.

Đề bài: Cho một mảng arr gồm n số nguyên đã được sắp xếp và một số nguyên target. Hãy tìm xem target có tồn tại trong mảng arr hay không. Nếu có, trả về chỉ số (index) của nó. Nếu không, trả về -1.

Ý tưởng: Áp dụng trực tiếp thuật toán Binary Search đã học. Chúng ta sẽ liên tục thu hẹp phạm vi tìm kiếm bằng cách so sánh target với phần tử ở giữa phạm vi hiện tại.

• Bắt đầu với phạm vi từ chỉ số low = 0 đến high = n - 1.
• Trong khi low <= high:
  • Tính chỉ số mid = low + (high - low) / 2. (Công thức này tránh tràn số tốt hơn so với (low + high) / 2 khi low và high lớn).
  • Nếu arr[mid] == target: Tìm thấy! Trả về mid.
  • Nếu arr[mid] < target: target nằm ở nửa bên phải. Cập nhật low = mid + 1.
  • Nếu arr[mid] > target: target nằm ở nửa bên trái. Cập nhật high = mid - 1.
• Nếu vòng lặp kết thúc mà không tìm thấy, trả về -1.

Code C++:

#include <iostream>
#include <vector>
#include <algorithm>

int basicBinarySearch(const std::vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // Tính chỉ số giữa

        if (arr[mid] == target) {
            return mid; // Tìm thấy target tại chỉ số mid
        } else if (arr[mid] < target) {
            low = mid + 1; // target nằm ở nửa bên phải, loại bỏ mid và nửa trái
        } else { // arr[mid] > target
            high = mid - 1; // target nằm ở nửa bên trái, loại bỏ mid và nửa phải
        }
    }

    return -1; // Không tìm thấy target trong mảng
}

int main() {
    std::vector<int> arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target1 = 23;
    int target2 = 40;

    int index1 = basicBinarySearch(arr, target1);
    if (index1 != -1) {
        std::cout << "Tim thay " << target1 << " tai chi so: " << index1 << std::endl; // Output: Tim thay 23 tai chi so: 5
    } else {
        std::cout << target1 << " khong co trong mang." << std::endl;
    }

    int index2 = basicBinarySearch(arr, target2);
    if (index2 != -1) {
        std::cout << "Tim thay " << target2 << " tai chi so: " << index2 << std::endl;
    } else {
        std::cout << target2 << " khong co trong mang." << std::endl; // Output: 40 khong co trong mang.
    }

    return 0;
}

Giải thích Code:

• Hàm basicBinarySearch nhận vào một vector arr (đã sắp xếp) và giá trị target cần tìm.
• low và high là hai con trỏ (chỉ số) xác định phạm vi tìm kiếm hiện tại. Ban đầu, chúng bao phủ toàn bộ mảng.
• Vòng lặp while (low <= high) tiếp tục chừng nào phạm vi tìm kiếm còn hợp lệ (chỉ số bắt đầu không vượt quá chỉ số kết thúc).
• mid = low + (high - low) / 2; tính toán chỉ số ở giữa. Đây là điểm mấu chốt để phân chia mảng làm hai phần.
• So sánh arr[mid] với target:
  • Nếu bằng, chúng ta đã tìm thấy target, hàm trả về mid.
  • Nếu arr[mid] nhỏ hơn target, nghĩa là target (nếu tồn tại) chỉ có thể nằm ở các chỉ số lớn hơn mid. Do đó, chúng ta loại bỏ nửa trái (bao gồm cả mid) bằng cách cập nhật low = mid + 1.
  • Nếu arr[mid] lớn hơn target, nghĩa là target (nếu tồn tại) chỉ có thể nằm ở các chỉ số nhỏ hơn mid. Do đó, chúng ta loại bỏ nửa phải (bao gồm cả mid) bằng cách cập nhật high = mid - 1.
• Nếu vòng lặp kết thúc (low > high), điều đó có nghĩa là phạm vi tìm kiếm đã trở nên rỗng mà vẫn không tìm thấy target, nên hàm trả về -1.

Bài tập 2: Tìm Vị trí Xuất hiện Đầu Tiên

Binary Search cơ bản trả về một chỉ số nếu tìm thấy target. Nhưng nếu target xuất hiện nhiều lần, làm sao để tìm chỉ số của lần xuất hiện đầu tiên?

Đề bài: Cho một mảng arr gồm n số nguyên đã được sắp xếp có thể chứa các phần tử trùng lặp, và một số nguyên target. Hãy tìm chỉ số của lần xuất hiện đầu tiên của target trong mảng. Nếu không tìm thấy, trả về -1.

Ý tưởng: Chúng ta vẫn sử dụng Binary Search. Khi tìm thấy một phần tử arr[mid] bằng target, chúng ta không dừng lại ngay. Thay vào đó, chúng ta lưu lại chỉ số mid như một ứng viên cho kết quả, và tiếp tục tìm kiếm ở nửa bên trái của mid (bao gồm cả mid) để xem có phần tử target nào xuất hiện ở chỉ số nhỏ hơn nữa không.

• Khởi tạo result = -1 để lưu chỉ số của lần xuất hiện đầu tiên tìm thấy.
• Thực hiện Binary Search như bình thường.
• Khi arr[mid] == target:
  • Cập nhật result = mid (lưu lại chỉ số hiện tại).
  • Thu hẹp phạm vi tìm kiếm về bên trái: high = mid - 1. (Chúng ta đang tìm kiếm lần xuất hiện đầu tiên, nên nếu tìm thấy một target, ta thử tìm ở bên trái nó).
• Nếu arr[mid] < target: target nằm ở nửa phải. Cập nhật low = mid + 1.
• Nếu arr[mid] > target: target nằm ở nửa trái. Cập nhật high = mid - 1.
• Sau khi vòng lặp kết thúc, result sẽ chứa chỉ số của lần xuất hiện đầu tiên (hoặc -1 nếu không tìm thấy).

Code C++:

#include <iostream>
#include <vector>
#include <algorithm>

int findFirstOccurrence(const std::vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int firstOccurrenceIndex = -1; // Biến lưu chỉ số lần xuất hiện đầu tiên

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            firstOccurrenceIndex = mid; // Lưu lại chỉ số này
            high = mid - 1;           // Tiếp tục tìm kiếm ở nửa trái (có thể có target ở chỉ số nhỏ hơn)
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else { // arr[mid] > target
            high = mid - 1;
        }
    }

    return firstOccurrenceIndex; // Trả về chỉ số đã lưu
}

int main() {
    std::vector<int> arr = {2, 5, 5, 5, 8, 12, 16, 23, 23, 38, 56};
    int target1 = 5;
    int target2 = 23;
    int target3 = 10;

    std::cout << "Vi tri xuat hien dau tien cua " << target1 << ": " << findFirstOccurrence(arr, target1) << std::endl; // Output: 1
    std::cout << "Vi tri xuat hien dau tien cua " << target2 << ": " << findFirstOccurrence(arr, target2) << std::endl; // Output: 7
    std::cout << "Vi tri xuat hien dau tien cua " << target3 << ": " << findFirstOccurrence(arr, target3) << std::endl; // Output: -1

    return 0;
}

Giải thích Code:

• Biến firstOccurrenceIndex được khởi tạo là -1. Nó sẽ lưu giữ chỉ số nhỏ nhất của target tìm được cho đến hiện tại.
• Khi arr[mid] == target, chúng ta đã tìm thấy một vị trí chứa target. Vị trí này có thể là lần xuất hiện đầu tiên hoặc không. Để chắc chắn tìm được lần đầu tiên, chúng ta lưu lại mid vào firstOccurrenceIndex và sau đó thu hẹp phạm vi tìm kiếm sang bên trái (high = mid - 1). Điều này đảm bảo rằng nếu có các phần tử target khác ở các chỉ số nhỏ hơn, thuật toán sẽ tìm thấy chúng trong các bước lặp tiếp theo và cập nhật firstOccurrenceIndex về một giá trị nhỏ hơn (gần 0 hơn).
• Các trường hợp arr[mid] < target và arr[mid] > target vẫn hoạt động như Binary Search cơ bản để thu hẹp phạm vi.
• Cuối cùng, firstOccurrenceIndex sẽ chứa chỉ số của lần xuất hiện đầu tiên của target (hoặc -1 nếu không tìm thấy bất kỳ lần nào).

Bài tập 3: Tìm Vị trí Xuất hiện Cuối Cùng

Ngược lại với bài tập trước, lần này chúng ta muốn tìm chỉ số của lần xuất hiện cuối cùng của target.

Đề bài: Cho một mảng arr gồm n số nguyên đã được sắp xếp có thể chứa các phần tử trùng lặp, và một số nguyên target. Hãy tìm chỉ số của lần xuất hiện cuối cùng của target trong mảng. Nếu không tìm thấy, trả về -1.

Ý tưởng: Tương tự như tìm lần xuất hiện đầu tiên, chúng ta cũng dùng Binary Search và lưu lại ứng viên. Tuy nhiên, khi tìm thấy arr[mid] == target, chúng ta sẽ tiếp tục tìm kiếm ở nửa bên phải của mid để xem có phần tử target nào xuất hiện ở chỉ số lớn hơn nữa không.

• Khởi tạo result = -1 để lưu chỉ số của lần xuất hiện cuối cùng tìm thấy.
• Thực hiện Binary Search như bình thường.
• Khi arr[mid] == target:
  • Cập nhật result = mid (lưu lại chỉ số hiện tại).
  • Thu hẹp phạm vi tìm kiếm về bên phải: low = mid + 1. (Chúng ta đang tìm kiếm lần xuất hiện cuối cùng, nên nếu tìm thấy một target, ta thử tìm ở bên phải nó).
• Nếu arr[mid] < target: target nằm ở nửa phải. Cập nhật low = mid + 1.
• Nếu arr[mid] > target: target nằm ở nửa trái. Cập nhật high = mid - 1.
• Sau khi vòng lặp kết thúc, result sẽ chứa chỉ số của lần xuất hiện cuối cùng (hoặc -1 nếu không tìm thấy).

Code C++:

#include <iostream>
#include <vector>
#include <algorithm>

int findLastOccurrence(const std::vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int lastOccurrenceIndex = -1; // Biến lưu chỉ số lần xuất hiện cuối cùng

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            lastOccurrenceIndex = mid; // Lưu lại chỉ số này
            low = mid + 1;            // Tiếp tục tìm kiếm ở nửa phải (có thể có target ở chỉ số lớn hơn)
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else { // arr[mid] > target
            high = mid - 1;
        }
    }

    return lastOccurrenceIndex; // Trả về chỉ số đã lưu
}

int main() {
    std::vector<int> arr = {2, 5, 5, 5, 8, 12, 16, 23, 23, 38, 56};
    int target1 = 5;
    int target2 = 23;
    int target3 = 10;

    std::cout << "Vi tri xuat hien cuoi cung cua " << target1 << ": " << findLastOccurrence(arr, target1) << std::endl; // Output: 3
    std::cout << "Vi tri xuat hien cuoi cung cua " << target2 << ": " << findLastOccurrence(arr, target2) << std::endl; // Output: 8
    std::cout << "Vi tri xuat hien cuoi cung cua " << target3 << ": " << findLastOccurrence(arr, target3) << std::endl; // Output: -1

    return 0;
}

Giải thích Code:

• Tương tự bài trước, lastOccurrenceIndex lưu trữ ứng viên cho chỉ số cuối cùng.
• Điểm khác biệt mấu chốt là khi arr[mid] == target, chúng ta lưu lại mid và sau đó cập nhật low = mid + 1. Điều này đẩy phạm vi tìm kiếm sang bên phải, để kiểm tra xem còn lần xuất hiện target nào ở chỉ số lớn hơn không. Nếu có, lastOccurrenceIndex sẽ được cập nhật trong các bước lặp sau.
• Cuối cùng, lastOccurrenceIndex sẽ giữ chỉ số lớn nhất của target tìm được.

Bài tập 4: Tìm Phần tử Nhỏ Nhất Lớn Hơn Hoặc Bằng Target (Lower Bound)

Đây là một ứng dụng rất phổ biến của Binary Search, thường được gọi là lower_bound.

Đề bài: Cho một mảng arr gồm n số nguyên đã được sắp xếp và một số nguyên target. Tìm chỉ số của phần tử đầu tiên trong mảng có giá trị lớn hơn hoặc bằng target. Nếu tất cả các phần tử đều nhỏ hơn target, trả về n (kích thước mảng).

Ý tưởng: Chúng ta tìm kiếm một vị trí mà tại đó, phần tử ở vị trí đó lớn hơn hoặc bằng target, và tất cả các phần tử trước nó đều nhỏ hơn target.

• Khởi tạo result = n (hoặc arr.size()) để lưu trữ ứng viên cho chỉ số thỏa mãn điều kiện. Giá trị khởi tạo n biểu thị trường hợp xấu nhất: không có phần tử nào thỏa mãn, hoặc phần tử đầu tiên thỏa mãn là sau phần tử cuối cùng.
• Thực hiện Binary Search.
• Tại mỗi bước, xem xét arr[mid]:
  • Nếu arr[mid] >= target: Phần tử tại mid thỏa mãn điều kiện "lớn hơn hoặc bằng target". Đây có thể là phần tử đầu tiên thỏa mãn, hoặc phần tử đầu tiên thỏa mãn nằm ở chỉ số nhỏ hơn mid. Do đó, chúng ta lưu lại mid vào result (vì nó là một ứng viên hợp lệ) và thu hẹp phạm vi tìm kiếm sang bên trái (high = mid - 1) để xem có thể tìm được chỉ số nhỏ hơn nào cũng thỏa mãn không.
  • Nếu arr[mid] < target: Phần tử tại mid quá nhỏ. Phần tử đầu tiên thỏa mãn (nếu có) phải nằm ở bên phải của mid. Do đó, chúng ta thu hẹp phạm vi tìm kiếm sang bên phải (low = mid + 1).
• Sau khi vòng lặp kết thúc, result sẽ chứa chỉ số của phần tử đầu tiên lớn hơn hoặc bằng target, hoặc n nếu không có phần tử nào như vậy.

Code C++:

#include <iostream>
#include <vector>
#include <algorithm>

int lowerBound(const std::vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int ans = arr.size(); // Lưu chỉ số của phần tử đầu tiên >= target. Khởi tạo là size()

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] >= target) {
            ans = mid;         // arr[mid] là ứng viên, lưu lại
            high = mid - 1;    // Tìm kiếm phần tử >= target ở nửa trái
        } else { // arr[mid] < target
            low = mid + 1;     // arr[mid] quá nhỏ, tìm kiếm ở nửa phải
        }
    }

    return ans; // Trả về chỉ số tìm được (hoặc size() nếu không có)
}

int main() {
    std::vector<int> arr = {2, 5, 5, 5, 8, 12, 16, 23, 23, 38, 56};
    int target1 = 5;
    int target2 = 6;
    int target3 = 23;
    int target4 = 60;
    int target5 = 1;

    std::cout << "lower_bound cua " << target1 << ": " << lowerBound(arr, target1) << std::endl; // Output: 1 (chi so cua 5 dau tien)
    std::cout << "lower_bound cua " << target2 << ": " << lowerBound(arr, target2) << std::endl; // Output: 4 (chi so cua 8)
    std::cout << "lower_bound cua " << target3 << ": " << lowerBound(arr, target3) << std::endl; // Output: 7 (chi so cua 23 dau tien)
    std::cout << "lower_bound cua " << target4 << ": " << lowerBound(arr, target4) << std::endl; // Output: 11 (size cua mang)
    std::cout << "lower_bound cua " << target5 << ": " << lowerBound(arr, target5) << std::endl; // Output: 0 (chi so cua 2)

    // Compare with std::lower_bound
    auto it1 = std::lower_bound(arr.begin(), arr.end(), target1);
    std::cout << "std::lower_bound cua " << target1 << ": " << std::distance(arr.begin(), it1) << std::endl;
    auto it4 = std::lower_bound(arr.begin(), arr.end(), target4);
     std::cout << "std::lower_bound cua " << target4 << ": " << std::distance(arr.begin(), it4) << std::endl;


    return 0;
}

Giải thích Code:

• Biến ans lưu trữ chỉ số kết quả tiềm năng. Nó được khởi tạo bằng arr.size(), là chỉ số "ngoài" mảng, biểu thị rằng chưa tìm thấy phần tử nào thỏa mãn hoặc tất cả đều nhỏ hơn target.
• Khi arr[mid] >= target, điều kiện "lớn hơn hoặc bằng" được thỏa mãn tại mid. mid là một ứng viên hợp lệ. Ta lưu nó vào ans. Tuy nhiên, vì ta muốn tìm phần tử đầu tiên thỏa mãn, có thể còn có các phần tử thỏa mãn ở chỉ số nhỏ hơn mid. Do đó, ta thu hẹp phạm vi tìm kiếm sang bên trái bằng cách đặt high = mid - 1.
• Khi arr[mid] < target, phần tử này quá nhỏ. Phần tử đầu tiên >= target (nếu có) chắc chắn phải nằm ở bên phải của mid. Ta loại bỏ mid và nửa trái bằng cách đặt low = mid + 1.
• Vòng lặp kết thúc khi low > high. Lúc này, ans sẽ giữ chỉ số nhỏ nhất mà tại đó arr[ans] lớn hơn hoặc bằng target. Nếu không có phần tử nào như vậy, ans vẫn giữ giá trị khởi tạo là arr.size().
• Hàm std::lower_bound trong thư viện <algorithm> của C++ thực hiện chính xác chức năng này và trả về một iterator. Sử dụng std::distance(arr.begin(), it) để lấy chỉ số từ iterator. Code của chúng ta mô phỏng lại hoạt động của nó.

Bài tập 5: Tìm Phần tử Nhỏ Nhất Lớn Hơn Target (Upper Bound)

Đây cũng là một ứng dụng phổ biến khác, thường được gọi là upper_bound.

Đề bài: Cho một mảng arr gồm n số nguyên đã được sắp xếp và một số nguyên target. Tìm chỉ số của phần tử đầu tiên trong mảng có giá trị lớn hơn hẳn target. Nếu tất cả các phần tử đều nhỏ hơn hoặc bằng target, trả về n (kích thước mảng).

Ý tưởng: Tương tự như lower_bound, chúng ta tìm một vị trí mà tại đó, phần tử ở vị trí đó lớn hơn hẳn target, và tất cả các phần tử trước nó đều nhỏ hơn hoặc bằng target.

• Khởi tạo result = n (hoặc arr.size()) để lưu trữ ứng viên.
• Thực hiện Binary Search.
• Tại mỗi bước, xem xét arr[mid]:
  • Nếu arr[mid] > target: Phần tử tại mid thỏa mãn điều kiện "lớn hơn hẳn target". Đây có thể là phần tử đầu tiên thỏa mãn, hoặc phần tử đầu tiên thỏa mãn nằm ở chỉ số nhỏ hơn mid. Lưu lại mid vào result và thu hẹp phạm vi tìm kiếm sang bên trái (high = mid - 1).
  • Nếu arr[mid] <= target: Phần tử tại mid quá nhỏ hoặc bằng target. Phần tử đầu tiên > target (nếu có) phải nằm ở bên phải của mid. Thu hẹp phạm vi tìm kiếm sang bên phải (low = mid + 1).
• Sau khi vòng lặp kết thúc, result sẽ chứa chỉ số của phần tử đầu tiên lớn hơn hẳn target, hoặc n nếu không có phần tử nào như vậy.

Code C++:

#include <iostream>
#include <vector>
#include <algorithm>

int upperBound(const std::vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int ans = arr.size(); // Lưu chỉ số của phần tử đầu tiên > target. Khởi tạo là size()

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] > target) {
            ans = mid;         // arr[mid] là ứng viên, lưu lại
            high = mid - 1;    // Tìm kiếm phần tử > target ở nửa trái
        } else { // arr[mid] <= target
            low = mid + 1;     // arr[mid] quá nhỏ hoặc bằng, tìm kiếm ở nửa phải
        }
    }

    return ans; // Trả về chỉ số tìm được (hoặc size() nếu không có)
}

int main() {
    std::vector<int> arr = {2, 5, 5, 5, 8, 12, 16, 23, 23, 38, 56};
    int target1 = 5;
    int target2 = 6;
    int target3 = 23;
    int target4 = 60;
    int target5 = 1;

    std::cout << "upper_bound cua " << target1 << ": " << upperBound(arr, target1) << std::endl; // Output: 4 (chi so cua 8)
    std::cout << "upper_bound cua " << target2 << ": " << upperBound(arr, target2) << std::endl; // Output: 4 (chi so cua 8)
    std::cout << "upper_bound cua " << target3 << ": " << upperBound(arr, target3) << std::endl; // Output: 9 (chi so cua 38)
    std::cout << "upper_bound cua " << target4 << ": " << upperBound(arr, target4) << std::endl; // Output: 11 (size cua mang)
    std::cout << "upper_bound cua " << target5 << ": " << upperBound(arr, target5) << std::endl; // Output: 0 (chi so cua 2)

    // Compare with std::upper_bound
    auto it1 = std::upper_bound(arr.begin(), arr.end(), target1);
    std::cout << "std::upper_bound cua " << target1 << ": " << std::distance(arr.begin(), it1) << std::endl;
     auto it4 = std::upper_bound(arr.begin(), arr.end(), target4);
    std::cout << "std::upper_bound cua " << target4 << ": " << std::distance(arr.begin(), it4) << std::endl;

    return 0;
}

Giải thích Code:

• Code này rất giống với lowerBound, chỉ khác ở điều kiện so sánh.
• ans được khởi tạo là arr.size().
• Khi arr[mid] > target, chúng ta tìm thấy một phần tử lớn hơn hẳn target. Lưu mid vào ans và tiếp tục tìm kiếm ở nửa trái (high = mid - 1) để xem có chỉ số nhỏ hơn nào thỏa mãn không.
• Khi arr[mid] <= target, phần tử này không lớn hơn hẳn target. Phần tử đầu tiên > target (nếu có) phải nằm ở bên phải. Loại bỏ nửa trái (bao gồm cả mid) bằng cách đặt low = mid + 1.
• Kết thúc vòng lặp, ans là chỉ số của phần tử đầu tiên lớn hơn hẳn target, hoặc arr.size() nếu không có.
• Hàm std::upper_bound trong STL cũng thực hiện điều này.

Bài tập 6: Tìm kiếm trên Mảng Xoay (Search in Rotated Sorted Array)

Đây là một bài tập kinh điển và nâng cao hơn một chút, đòi hỏi sự hiểu biết sâu hơn về cách Binary Search hoạt động.

Đề bài: Cho một mảng arr ban đầu được sắp xếp tăng dần, nhưng sau đó đã bị xoay tại một điểm không xác định. Ví dụ: [0, 1, 2, 4, 5, 6, 7] có thể trở thành [4, 5, 6, 7, 0, 1, 2]. Cho một target và mảng arr đã xoay, tìm chỉ số của target trong mảng. Nếu không tìm thấy, trả về -1. Giả định không có các phần tử trùng lặp trong mảng.

Ý tưởng: Mảng đã xoay vẫn giữ tính chất quan trọng: một trong hai nửa (từ low đến mid hoặc từ mid đến high) vẫn sẽ được sắp xếp. Chúng ta cần xác định nửa nào được sắp xếp và kiểm tra xem target có nằm trong nửa đó hay không để quyết định tìm kiếm ở bên trái hay bên phải.

• Bắt đầu với phạm vi low = 0 và high = n - 1.
• Trong khi low <= high:
  • Tính mid.
  • Nếu arr[mid] == target, tìm thấy, trả về mid.
  • Xác định nửa nào được sắp xếp:
    • Kiểm tra nửa trái: Nếu arr[low] <= arr[mid], nghĩa là phần từ low đến mid được sắp xếp tăng dần.
      • Nếu target nằm trong phạm vi này (arr[low] <= target && target < arr[mid]), tìm kiếm ở nửa trái: high = mid - 1.
      • Ngược lại, target phải nằm ở nửa phải: low = mid + 1.
    • Kiểm tra nửa phải: (Nếu nửa trái không được sắp xếp, thì nửa phải arr[mid] đến arr[high] phải được sắp xếp). Nếu arr[low] > arr[mid] (hoặc chỉ cần dùng else từ điều kiện nửa trái), nghĩa là phần từ mid đến high được sắp xếp tăng dần.
      • Nếu target nằm trong phạm vi này (arr[mid] < target && target <= arr[high]), tìm kiếm ở nửa phải: low = mid + 1.
      • Ngược lại, target phải nằm ở nửa trái: high = mid - 1.
• Nếu vòng lặp kết thúc mà không tìm thấy, trả về -1.

Code C++:

#include <iostream>
#include <vector>
#include <algorithm>

int searchInRotatedArray(const std::vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid; // Tìm thấy target
        }

        // Xác định nửa nào được sắp xếp
        if (arr[low] <= arr[mid]) { // Nửa trái (từ low đến mid) được sắp xếp
            if (target >= arr[low] && target < arr[mid]) {
                // Target nằm trong nửa trái được sắp xếp
                high = mid - 1;
            } else {
                // Target nằm ở nửa phải (không được sắp xếp hoặc nằm sau điểm xoay)
                low = mid + 1;
            }
        } else { // Nửa phải (từ mid đến high) được sắp xếp
            if (target > arr[mid] && target <= arr[high]) {
                // Target nằm trong nửa phải được sắp xếp
                low = mid + 1;
            } else {
                // Target nằm ở nửa trái (không được sắp xếp hoặc nằm trước điểm xoay)
                high = mid - 1;
            }
        }
    }

    return -1; // Không tìm thấy target
}

int main() {
    std::vector<int> arr1 = {4, 5, 6, 7, 0, 1, 2};
    int target1_1 = 0;
    int target1_2 = 3;

    std::vector<int> arr2 = {1, 3};
    int target2_1 = 3;

    std::cout << "Trong [4,5,6,7,0,1,2]: Tim " << target1_1 << " -> " << searchInRotatedArray(arr1, target1_1) << std::endl; // Output: 4
    std::cout << "Trong [4,5,6,7,0,1,2]: Tim " << target1_2 << " -> " << searchInRotatedArray(arr1, target1_2) << std::endl; // Output: -1
    std::cout << "Trong [1,3]: Tim " << target2_1 << " -> " << searchInRotatedArray(arr2, target2_1) << std::endl; // Output: 1

    return 0;
}

Giải thích Code:

• Điểm khó của bài toán này là mảng bị "gãy" tại điểm xoay, nên không phải toàn bộ mảng từ low đến high đều được sắp xếp.
• Tuy nhiên, một trong hai nửa (từ low đến mid hoặc từ mid đến high) chắc chắn sẽ được sắp xếp. Ta kiểm tra điều này bằng cách so sánh arr[low] và arr[mid].
  • Nếu arr[low] <= arr[mid], thì nửa trái là phần được sắp xếp.
  • Ngược lại (arr[low] > arr[mid]), thì nửa phải là phần được sắp xếp.
• Nếu nửa trái được sắp xếp:
  • Ta kiểm tra xem target có nằm trong phạm vi giá trị của nửa trái được sắp xếp hay không (arr[low] <= target && target < arr[mid]).
  • Nếu có, ta biết target (nếu tồn tại) phải nằm ở nửa trái, nên ta thu hẹp phạm vi tìm kiếm sang trái (high = mid - 1).
  • Nếu không, target phải nằm ở nửa phải (phần không được sắp xếp), nên ta thu hẹp phạm vi tìm kiếm sang phải (low = mid + 1).
• Nếu nửa phải được sắp xếp:
  • Ta kiểm tra xem target có nằm trong phạm vi giá trị của nửa phải được sắp xếp hay không (arr[mid] < target && target <= arr[high]).
  • Nếu có, target phải nằm ở nửa phải, thu hẹp sang phải (low = mid + 1).
  • Nếu không, target phải nằm ở nửa trái (phần không được sắp xếp), thu hẹp sang trái (high = mid - 1).
• Quá trình này tiếp diễn cho đến khi tìm thấy target hoặc phạm vi tìm kiếm trở nên rỗng.

Bài tập ví dụ:

Hoán vị và Phép đổi chỗ

Trong một buổi thảo luận trực tuyến về thuật toán, FullHouse Dev đã gặp một bài toán thú vị liên quan đến hoán vị và phép đổi chỗ. Với sự hỗ trợ của internet và kiến thức sẵn có, họ bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

FullHouse Dev được cung cấp một mảng \(A\) có \(n\) phần tử nguyên. Họ có thể thực hiện phép toán sau đây trên mảng \(A\) bao nhiêu lần tùy ý:

Chọn hai chỉ số \(i\) và \(j\) sao cho \(i < j\), sau đó giảm \(A[i]\) đi \(1\) và tăng \(A[j]\) lên \(1\).

Nhiệm vụ của nhóm là xác định xem có thể biến đổi mảng \(A\) thành một hoán vị của các số từ \(1\) đến \(n\) hay không.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng bộ test.
• Với mỗi bộ test:
  • Dòng đầu tiên chứa một số nguyên \(n\) - độ dài của mảng \(A\).
  • Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, ..., A_n\) - các phần tử của mảng \(A\).

OUTPUT FORMAT:

• Với mỗi bộ test, in ra "YES" nếu có thể biến đổi mảng \(A\) thành một hoán vị, ngược lại in ra "NO".

Ràng buộc:

• \(1 \leq T \leq 10^5\)
• \(1 \leq n \leq 10^5\)
• \(1 \leq A_i \leq 10^9\)
• Tổng của \(n\) trong tất cả các bộ test không vượt quá \(10^6\)

Ví dụ

INPUT

2
4
3 3 2 2
3
2 1 2

OUTPUT

YES
NO

Giải thích

• Ở bộ test đầu tiên, FullHouse Dev có thể áp dụng phép toán trên các chỉ số \(1\) và \(4\), biến mảng thành \([2, 3, 2, 3]\), sau đó áp dụng trên các chỉ số \(2\) và \(3\), thu được \([2, 2, 3, 3]\), là một hoán vị của các số từ 1 đến 4.
• Ở bộ test thứ hai, không thể biến đổi mảng thành một hoán vị của các số từ 1 đến 3.

FullHouse Dev nhận ra rằng bài toán này không chỉ đòi hỏi kiến thức về thuật toán mà còn cần sự sáng tạo trong việc áp dụng các phép biến đổi. Họ quyết định chia sẻ bài toán này trên diễn đàn lập trình để thảo luận thêm với cộng đồng. Tuyệt vời! Đây là một bài toán kinh điển liên quan đến phép biến đổi và tính khả thi. Hướng giải ngắn gọn sẽ tập trung vào các đại lượng bất biến hoặc giới hạn của phép biến đổi.

1. Phân tích phép biến đổi: Phép toán "giảm A[i] đi 1 và tăng A[j] lên 1 với i < j" có hai tính chất quan trọng:

   • Tổng không đổi: Tổng của tất cả các phần tử trong mảng A không thay đổi sau mỗi phép toán.
   • Di chuyển giá trị: Về mặt hiệu quả, phép toán này chỉ có thể di chuyển "giá trị" từ một vị trí có chỉ số nhỏ hơn (i) sang một vị trí có chỉ số lớn hơn (j). Giá trị không thể di chuyển ngược lại (từ j sang i với i < j).

2. Phân tích đích đến: Đích đến là một hoán vị bất kỳ của các số từ 1 đến n.

   • Tổng đích: Tổng của các phần tử trong đích đến luôn là tổng của các số từ 1 đến n, tức là 1 + 2 + ... + n = n * (n + 1) / 2.

3. Điều kiện cần dựa trên tổng: Vì tổng các phần tử không đổi trong quá trình biến đổi, điều kiện cần đầu tiên là tổng các phần tử của mảng A ban đầu phải bằng tổng của các số từ 1 đến n.

   • Tính tổng mảng A ban đầu.
   • Tính tổng đích n * (n + 1) / 2.
   • Nếu hai tổng này khác nhau, không thể biến đổi được -> "NO".

4. Điều kiện cần dựa trên tiền tố: Do phép biến đổi chỉ có thể di chuyển giá trị từ trái sang phải (từ chỉ số nhỏ sang chỉ số lớn), lượng giá trị trong bất kỳ đoạn tiền tố nào của mảng (A[1] + ... + A[k]) chỉ có thể giảm đi hoặc giữ nguyên. Nó không bao giờ có thể tăng lên do giá trị từ các vị trí j > k chuyển đến. Để có thể biến đổi mảng A thành một hoán vị của 1 đến n, lượng giá trị trong đoạn tiền tố A[1] + ... + A[k] của mảng ban đầu phải đủ lớn để tạo ra ít nhất tổng của k số nhỏ nhất trong tập {1, ..., n} (là 1, 2, ..., k) tại các vị trí từ 1 đến k trong hoán vị đích.

   • Tổng tối thiểu của k phần tử đầu tiên trong bất kỳ hoán vị nào của 1 đến n là tổng của 1 đến k, tức là k * (k + 1) / 2.
   • Điều kiện cần thứ hai là tổng tiền tố của mảng A ban đầu tại mọi vị trí k phải lớn hơn hoặc bằng tổng tiền tố tối thiểu của k số đầu tiên trong tập 1..n.
   • Tính tổng tiền tố S_A[k] = A[1] + ... + A[k] cho k = 1, ..., n.
   • Tính tổng tiền tố đích tối thiểu S_{min\_target}[k] = k * (k + 1) / 2 cho k = 1, ..., n.
   • Kiểm tra xem S_A[k] \ge S_{min\_target}[k] với mọi k từ 1 đến n. Nếu điều này không đúng với bất kỳ k nào, không thể biến đổi được -> "NO".

5. Kết hợp và tính đủ: Nếu cả hai điều kiện trên đều được thỏa mãn (tổng bằng nhau và mọi tổng tiền tố của A đều lớn hơn hoặc bằng tổng tiền tố tối thiểu của 1..n), thì mảng A có thể biến đổi được thành một hoán vị của 1 đến n. Sự đủ của các điều kiện này có thể được giải thích một cách trực quan: Điều kiện tổng đảm bảo lượng giá trị tổng thể là đúng. Điều kiện tiền tố đảm bảo rằng không bao giờ có "thiếu hụt" không thể bù đắp ở các vị trí đầu. Lượng "dư thừa" ở các tiền tố (khi S_A[k] > S_{min\_target}[k]) có thể được dịch chuyển sang phải bằng phép toán, lấp đầy bất kỳ "thiếu hụt" nào có thể có ở các vị trí sau (do điều kiện tổng và tiền tố, thiếu hụt này không thể vượt quá lượng dư thừa tích lũy từ trái sang).

6. Thuật toán:

   • Đọc n và mảng A.
   • Sử dụng kiểu dữ liệu long long cho các tổng để tránh tràn số.
   • Tính tổng đích target_sum = (long long)n * (n + 1) / 2.
   • Khởi tạo current_sum = 0 và possible = true.
   • Duyệt qua mảng A từ i = 0 đến n-1:
     • Cập nhật current_sum += A[i].
     • Tính tổng tiền tố đích tối thiểu cho vị trí hiện tại (chỉ số 0 tương ứng với k=1, chỉ số i tương ứng với k=i+1): min_target_prefix_sum = (long long)(i + 1) * (i + 2) / 2.
     • Nếu current_sum < min_target_prefix_sum, đặt possible = false và thoát vòng lặp.
   • Sau vòng lặp, nếu possible là true và current_sum == target_sum, in ra "YES".
   • Ngược lại, in ra "NO". (Lưu ý: điều kiện current_sum == target_sum được kiểm tra tự động ở cuối vòng lặp k=n-1 nếu possible vẫn là true, vì min_target_prefix_sum cho k=n chính là target_sum).

Làm thêm nhiều bài tập miễn phí tại đây