Các Thuật Toán Tìm Kiếm Trong C++

Trong hầu hết các hệ quản lý dữ liệu, việc tìm kiếm là một hoạt động quan trọng để khai thác các thông tin khác nhau. Khi xây dựng một hệ quản lý thông tin trên máy tính, việc nắm vững các thuật toán tìm kiếm và sắp xếp dữ liệu là rất quan trọng. Hãy cùng tìm hiểu về các thuật toán tìm kiếm phổ biến trong ngôn ngữ lập trình C++.

1. Thuật Toán Tìm Kiếm Là Gì

Tìm kiếm là quá trình tìm một phần tử trong một tập hợp dựa vào một miêu tả nào đó. Đối với ví dụ tìm đồng 10k trong một đống tiền từ 10k đến 100k, đó gọi là tìm kiếm.

Bạn đang xem: Các Thuật Toán Tìm Kiếm Trong C++

Trong trường hợp tập hợp đã được sắp xếp, việc tìm kiếm sẽ nhanh hơn. Ví dụ, nếu đống tiền từ 10k đến 100k đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần, việc tìm tờ 10k sẽ dễ dàng hơn. Tuy nhiên, nếu đống tiền là một tập hợp không có thứ tự, việc tìm kiếm sẽ mất nhiều thời gian hơn.

Thuật toán tìm kiếm được sử dụng để tìm kiếm một phần tử trong danh sách cho trước theo một tiêu chí nhất định. Hai thuật toán tìm kiếm phổ biến là tìm kiếm tuyến tính và tìm kiếm nhị phân.

• Thuật Toán Tìm Kiếm Tuyến Tính: Thuật toán này được sử dụng để tìm kiếm trong một tập hợp chưa được sắp xếp, giống với đống tiền chưa được sắp xếp ở ví dụ trên. Thuật toán tìm kiếm tuyến tính là một phương pháp tìm kiếm một phần tử cho trước trong một danh sách bằng cách duyệt lần lượt từng phần tử của danh sách đó cho đến khi tìm thấy giá trị mong muốn hoặc đã duyệt qua toàn bộ danh sách.

Ví dụ: Tìm kiếm phần tử x trong mảng []

Input: A[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170} x = 110;
Output: Element x is present at position 6

Input: A[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170} x = 175;
Output: Element x is not present in A[].

    Mã giả:

    Phiên bản lặp không tự nhiên
    - Đi qua từng phần tử trong danh sách:
        - Nếu phần tử đó có giá trị mong muốn, kết thúc tìm kiếm và trả về vị trí của phần tử.
    - Trả về 'Δ'

    Nếu danh sách được lưu trữ dưới dạng mảng, vị trí của phần tử mà ta tìm kiếm có thể là chỉ số của nó trong mảng, còn giá trị Δ có thể là chỉ số nằm trước phần tử đầu tiên (0 hoặc -1 tùy vào danh sách).

    Nếu danh sách được lưu trữ dưới dạng danh sách liên kết, vị trí của phần tử được trả về có thể là địa chỉ của nó, còn giá trị Δ có thể là giá trị null.

    Phiên bản đệ quy
    - Nếu danh sách rỗng, trả về Λ;
    - Ngược lại
        - Nếu phần tử đầu tiên trong danh sách có giá trị mong muốn
            - Trả về vị trí của nó.
        - Ngược lại
            - Tiếp tục tìm kiếm giá trị trong phần còn lại của danh sách và trả về kết quả.

    Sử dụng phần tử cầm canh
    - Thêm phần tử cần tìm và cuối danh sách như một phần tử cầm canh (sentinel):
    - Gán A[n + 1] = x.
    - Gán i = 1.
    - Lặp lại quy trình sau:
        - Nếu A[i] = x,
            - Kết thúc vòng lặp.
        - Gán i = i + 1.
    - Trả về i.

    Việc thêm phần tử cầm canh giúp giảm số lần so sánh chỉ mục hiện tại i với số phần tử n ở mỗi vòng lặp. Tuy nhiên, điều này chỉ áp dụng khi vị trí cuối cùng của danh sách tồn tại nhưng chưa được sử dụng.

    Viết thuật toán tìm kiếm tuyến tính với ngôn ngữ lập trình C, C++, Java, Python3

    Tìm kiếm tuyến tính với C++:

    ```cpp
    #include
    using namespace std;
    int search(int arr[], int n, int x)
    {
        int i;
        for (i = 0; i < n; i++)
            if (arr[i] == x)
                return i;
        return -1;
    }
    int main(void)
    {
        int arr[] = { 2, 3, 4, 10, 40 };
        int x = 10;
        int n = sizeof(arr) / sizeof(arr[0]);
        int result = search(arr, n, x);
        (result == -1) ? cout<<"Element is not present in array"
                    : cout<<"Element is present at index " <
    int search(int arr[], int n, int x)
    {
        int i;
        for (i = 0; i < n; i++)
            if (arr[i] == x)
                return i;
        return -1;
    }
    int main(void)
    {
        int arr[] = { 2, 3, 4, 10, 40 };
        int x = 10;
        int n = sizeof(arr) / sizeof(arr[0]);
        int result = search(arr, n, x);
        (result == -1)
            ? printf("Element is not present in array")
            : printf("Element is present at index %d", result);
        return 0;
    }
    ```

    Tìm kiếm tuyến tính với Python3:

    ```python
    def search(arr, n, x):
        for i in range (0, n):
            if (arr[i] == x):
                return i;
        return -1;
    # Driver Code
    arr = [ 2, 3, 4, 10, 40 ];
    x = 10;
    n = len(arr);
    result = search(arr, n, x)
    if(result == -1):
        print("Element is not present in array")
    else:
        print("Element is present at index", result);
    ```

    Tìm kiếm tuyến tính với Java:

    ```java
    class GFG
    {
        // This function returns index of element x in arr[]
        static int search(int arr[], int x)
        {
            int n = arr.length;
            for(int i = 0; i < n; i++)
            {
                if(arr[i] == x)
                    return i;
            }
            return -1;
        }
        public static void main(String args[])
        {
            int arr[] = { 2, 3, 4, 10, 40 };
            int x = 10;
            int result = search(arr, x);
            if(result == -1)
                System.out.print("Element is not present in array");
            else
                System.out.print("Element is present at index " + result);
        }
    }
    ```

    Tìm kiếm tuyến tính với PHP:

    ```php
    
    ```

    Tìm kiếm tuyến tính với C#:

    ```csharp
    using System;
    class GFG
    {
        public static int search(int[] arr, int x)
        {
            int n = arr.Length;
            for(int i = 0; i < n; i++)
            {
                if(arr[i] == x)
                    return i;
            }
            return -1;
        }
        public static void Main()
        {
            int[] arr = { 2, 3, 4, 10, 40 };
            int x = 10;
            int result = search(arr, x);
            if(result == -1)
                Console.WriteLine("Element is not present in array");
            else
                Console.WriteLine("Element is present at index "+ result);
        }
    }
    ```

    Chạy thử và xem kết quả:

    ```
    Element is present at index 3
    ```

2. Các Thuật Toán Tìm Kiếm Trong C++

Trong bài viết này, chúng ta sẽ giới thiệu đến các thuật toán tìm kiếm phổ biến nhất trong C++. Hãy bắt đầu tìm hiểu về các thuật toán tìm kiếm này.

2.1. Thuật Toán Tìm Kiếm Tuyến Tính

Thuật toán tìm kiếm tuyến tính (linear search) hay còn gọi là thuật toán tìm kiếm tuần tự (Sequential search) là một phương pháp tìm kiếm một phần tử cho trước trong một danh sách bằng cách duyệt lần lượt từng phần tử của danh sách đó cho đến lúc tìm thấy giá trị mong muốn hay đã duyệt qua toàn bộ danh sách.

Thuật toán tìm kiếm tuyến tính là một giải thuật rất đơn giản khi hiện thực. Giải thuật này tỏ ra khá hiệu quả khi cần tìm kiếm phần tử trên một danh sách đủ nhỏ hoặc một danh sách chưa sắp thứ tự đơn giản. Trong trường hợp cần tìm kiếm nhiều lần, dữ liệu thường được xử lý một lần trước khi tìm kiếm: có thể được sắp xếp theo thứ tự, hoặc được xây dựng theo một cấu trúc dữ liệu đặc trưng cho giải thuật hiệu quả hơn,…

Bài toán: Cho một mảng mảng [] gồm n phần tử, hãy viết hàm để tìm kiếm một phần tử x đã cho trong mảng [].

Tìm kiếm tuyến tính trong C++:

#include
using namespace std;
int search(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
    return -1;
}
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = search(arr, n, x);
    (result == -1) ? cout<<"Element is not present in array"
                : cout<<"Element is present at index " <

#include 
int search(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
    return -1;
}
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = search(arr, n, x);
    (result == -1)
        ? printf("Element is not present in array")
        : printf("Element is present at index %d", result);
    return 0;
}

def search(arr, n, x):
    for i in range (0, n):
        if (arr[i] == x):
            return i;
    return -1;
# Driver Code
arr = [ 2, 3, 4, 10, 40 ];
x = 10;
n = len(arr);
result = search(arr, n, x)
if(result == -1):
    print("Element is not present in array")
else:
    print("Element is present at index", result);

class GFG
{
    // This function returns index of element x in arr[]
    static int search(int arr[], int x)
    {
        int n = arr.length;
        for(int i = 0; i < n; i++)
        {
            if(arr[i] == x)
                return i;
        }
        return -1;
    }
    public static void main(String args[])
    {
        int arr[] = { 2, 3, 4, 10, 40 };
        int x = 10;
        int result = search(arr, x);
        if(result == -1)
            System.out.print("Element is not present in array");
        else
            System.out.print("Element is present at index " + result);
    }
}

using System;
class GFG
{
    public static int search(int[] arr, int x)
    {
        int n = arr.Length;
        for(int i = 0; i < n; i++)
        {
            if(arr[i] == x)
                return i;
        }
        return -1;
    }
    public static void Main()
    {
        int[] arr = { 2, 3, 4, 10, 40 };
        int x = 10;
        int result = search(arr, x);
        if(result == -1)
            Console.WriteLine("Element is not present in array");
        else
            Console.WriteLine("Element is present at index "+ result);
    }
}

Element is present at index 3

#include
using namespace std;
int search(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
    return -1;
}
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = search(arr, n, x);
    (result == -1) ? cout<<"Element is not present in array"
                : cout<<"Element is present at index " <

#include 
int search(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
    return -1;
}
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = search(arr, n, x);
    (result == -1) ? printf("Element is not present in array")
                : printf("Element is present at index %d", result);
    return 0;
}

def search(arr, n, x):
    for i in range (0, n):
        if (arr[i] == x):
            return i;
    return -1;
# Driver Code
arr = [ 2, 3, 4, 10, 40 ];
x = 10;
n = len(arr);
result = search(arr, n, x)
if(result == -1):
    print("Element is not present in array")
else:
    print("Element is present at index", result);

class GFG
{
    // This function returns index of element x in arr[]
    static int search(int arr[], int x)
    {
        int n = arr.length;
        for(int i = 0; i < n; i++)
        {
            if(arr[i] == x)
                return i;
        }
        return -1;
    }
    public static void main(String args[])
    {
        int arr[] = { 2, 3, 4, 10, 40 };
        int x = 10;
        int result = search(arr, x);
        if(result == -1)
            System.out.print("Element is not present in array");
        else
            System.out.print("Element is present at index " + result);
    }
}