[C++] Các thuật toán tìm kiếm cơ bản thường sử dụng

Thuật toán tìm kiếm nhị phân (binary search) (code này chỉ áp dụng cho mảng đã sắp xếp tăng dần)

Mã: Chọn tất cả

#include <iostream>


using namespace std;


int BinarySearch(int A[], int n, int x)
{
    int left = 0;
    int right = n - 1;
    int mid;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (A[mid] == x)
            return mid; // tìm thấy x, trả về mid là vị trí của x trong mảng A
        if (A[mid] > x)
            right = mid - 1; // Giới hạn khoảng tìm kiếm lại là nửa khoảng trước
        else if (A[mid] < x)
            left = mid + 1; // Giới hạn khoảng tìm kiếm lại là nửa khoảng sau
    }
    return -1; // không tìm thấy x
}

int main()
{

    int arr[] {-33,-26,-5,1,2,3,7,12,32,45,53,71,80,99,100};

    int n = sizeof(arr) / sizeof(arr[0]); // so luong phan tu trong mang

    cout << "So luong phan tu trong mang: " << n << endl;

    cout << BinarySearch(arr, n, -5);

    return 0;
}