Tìm kiếm nhị phân trong C và C++ – Chạy online

Tìm kiếm nhị phân là gì?

Binary search bỏ một nửa phạm vi sau mỗi phép so sánh.

Tìm trong dữ liệu đã sort với thời gian logarithmic.

Điểm quan trọng

Test input rỗng, một phần tử, trùng lặp và đã sắp xếp.
Tách correctness khỏi optimization.
Ưu tiên standard library trong code production.

Mô phỏng Tìm kiếm nhị phân

O(log n)

Nhấn Phát hoặc Từng bước để theo dõi từng phép so sánh và thay đổi dữ liệu.

Code ví dụ bằng C và C++

C

Chạy code →

main.c

#include <stdio.h>

int search(const int *values, int size, int target) {
    int low = 0;
    int high = size - 1;
    while (low <= high) {
        int middle = low + (high - low) / 2;
        if (values[middle] == target) return middle;
        if (values[middle] < target) low = middle + 1;
        else high = middle - 1;
    }
    return -1;
}

int main(void) {
    int values[] = {3, 7, 11, 16, 23, 28};
    printf("index=%d\n", search(values, 6, 23));
}

Output dự kiến

index=4

C++

Chạy code →

main.cpp

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

int main() {
    std::vector values{3, 7, 11, 16, 23, 28};
    auto match = std::lower_bound(values.begin(), values.end(), 23);
    std::cout << "index="
              << std::distance(values.begin(), match) << '\n';
}

Output dự kiến

index=4

So sánh C và C++

Input bắt buộc sorted. Loop C và std::lower_bound đều O(log n) trên random-access range.

C

Loop, pointer, length và buffer tạm được viết tường minh.

C++

Iterator và standard algorithm tách operation khỏi cách lưu dữ liệu.

Bài tập mở rộng

Chạy cả hai phiên bản rồi thay đổi để quan sát khác biệt về bảo đảm của từng ngôn ngữ.

Trace từng phép so sánh trên giấy.
Test duplicate và extreme value.
Benchmark code tự viết với standard library.