[C++] Các thuật toán tìm kiếm cơ bản thường sử dụng : C, C++, C#, Java, Python, PHP, JS, SQL ...

nghiammo1992 (Off) ♂️
Cấp độ:

♡15♡
Like: 4342/14570
Online: ✨1/5321✨
Tiếu Ngạo ⚡5/60⚡
☀️2/30☀️ 🌟66/1087🌟

#1 13/09/2021 10:48

Thuật toán tìm kiếm tuyến tính (linear search)

Mã:

#include <iostream>


using namespace std;


int LinearSearch(int A[], int n, int x)
{
    for (int i = 0; i < n; i++)
        if (A[i] == x)
            return i;
    return -1; // duyệt hết mảng, không tìm thấy x
}


int main()
{

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

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

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

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

    return 0;
}

(Google Chrome 94.0.460)

PM|Trích|Like|Sửa|Xóa|Báo cáo|Cảnh cáo

_______________
Diễn đàn chia sẻ kiến thức máy tính:
KETNOI123.COM

Ấn hiện ra để xem chữ ký của mình:

nghiammo1992 (Off) ♂️
Cấp độ:

♡15♡
Like: 4342/14570
Online: ✨1/5321✨
Tiếu Ngạo ⚡5/60⚡
☀️2/30☀️ 🌟66/1087🌟

#2 13/09/2021 10:56

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ã:

#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;
}

(Google Chrome 94.0.460)

PM|Trích|Like|Sửa|Xóa|Báo cáo|Cảnh cáo

_______________
Diễn đàn chia sẻ kiến thức máy tính:
KETNOI123.COM

Ấn hiện ra để xem chữ ký của mình:

nghiammo1992 (Off) ♂️
Cấp độ:

♡15♡
Like: 4342/14570
Online: ✨1/5321✨
Tiếu Ngạo ⚡5/60⚡
☀️2/30☀️ 🌟66/1087🌟

#3 13/09/2021 11:03

Thuật toán tìm kiếm nội suy (interpolation search) (code này chỉ áp dụng cho mảng đã sắp xếp tăng dần)

Mã:

#include <iostream>


using namespace std;


int InterpolationSearch(int A[], int n, int x)
{
    int left = 0;
    int right = n - 1;
    int mid;
    while (left <= right && x >= A[left] && x <= A[right])
    {
        mid = left + (right - left) * (x - A[left]) / (A[right] - A[left]);
        if (A[mid] == x)
            return mid;
        if (A[mid] > x)
            right = mid - 1;
        else if (A[mid] < x)
            left = mid + 1;
    }
    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 << InterpolationSearch(arr, n, -5);

    return 0;
}

(Google Chrome 94.0.460)

PM|Trích|Like|Sửa|Xóa|Báo cáo|Cảnh cáo

Sửa lần cuối: nghiammo1992 03/06/2022 02:50

_______________
Diễn đàn chia sẻ kiến thức máy tính:
KETNOI123.COM

Ấn hiện ra để xem chữ ký của mình: