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, thao tác tìm kiếm thường được thực hiện nhất để khai thác thông tin khác nhau. Bởi vậy, khi xây dựng một hệ quản lý thông tin trên máy tính, bên cạnh các thuật toán tìm kiếm, các thuật toán sắp xếp dữ liệu cũng là một trong những chủ đề được quan tâm hàng đầu. Hãy cùng mình tìm hiểu về thuật toán tìm kiếm phổ biến nhé.

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ử nằm trong một tập hợp nhiều phần tử dựa vào một miêu tả nào đó. Ví dụ bạn cần tìm đồng 10k trong một đống tiền từ 10k đến 100k thì quá trình đó ta gọi là tìm kiếm.

Nếu một tập hợp đã được sắp xếp thì quá trình tìm kiếm trong tập hợp đó sẽ nhanh hơn. Ở thí dụ trên nếu đống tiền từ 10k đến 100k đã được sắp xếp tăng dần hoặc giảm dần thì ta cực kỳ dễ dàng tìm kiếm tờ 10k. Nhưng nếu đó là 1 đống tiền lộn xộn thì bạn sẽ mất nhiều thời gian để xử lý chúng.

Vậy thuật toán tìm kiếm là thuật toán dùng để kiếm tìm phần tử trong 1 danh sách cho trước theo một tiêu chí nhất định. Chúng ta thường sử dụng hai thuật toán đó là thuật toán tìm kiếm tuyến tính và thuật toán tìm kiếm nhị phân.

Thuật toán tìm kiếm tuyến tính là quá trình tìm kiếm trong một tập hợp chưa sắp xếp, giống với đống tiền chưa được sắp xếp ở ví dụ trên. Còn thuật toán tìm kiếm nhị phân là quá trình tìm kiếm trong một dãy đã được sắp xếp. Cả hai thuật toán đều có những ưu và nhược điểm khác nhau.

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

Trong bài viết này, mình sẽ giới thiệu đến các bạn các thuật toán tìm kiếm trong C++ phổ biến nhất. Giờ hãy bắt đầu tìm hiểu về các thuật toán tìm kiếm này nhé!

+ 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.

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 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 [].

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

Ví dụ:
Đầu vào: mảng A[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170} x = 110;
Đầu ra: 6 Phần tử x có mặt ở vị trí số 6

Đầu vào: mảng A[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170} x = 175;
Đầu ra: -1 Phần tử x không có trong mảng A[].

Mã giả
Phiên bản lặp tự nhiên
Đây là phiên bản hay gặp nhất của giải thuật này, kết quả trả về sẽ là vị trí của phần tử cần tìm hoặc một giá trị Δ thể hiện việc không tìm thấy phần tử trong danh sách đó.

1. For each item in the list:
   1. if that item has the desired value,
      1. stop the search and return the item's location.
2. Return 'Δ'

Nếu danh sách được lưu trữ dưới dạng mảng, vị trí của phần tử cần tì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 là một danh sách liên kết, vị trí của phần tử được trả về có thể nằm dưới dạng địa chỉ của no, còn giá trị Δ có thể là giá trị null.

Phiên bản đệ quy
Đây là phiên bản đệ quy khi hiện thực giải thuật tìm kiếm tuần tự.

1. if the list is empty, return Λ;
2. else
   1. if the first item of the list has the desired value
      1. return its location;
   2. else
      1. search the value in the remainder of the list, and return the result.

Sử dụng phần tử cầm canh
Một phương pháp được sử dụng để cải thiện hiệu quả của giải thuật là chèn phần tử muốn tìm kiếm và cuối danh sách như một phần tử cầm canh (sentinel) như được trình bày dưới đây:

1. Set A[n + 1] to x.
2. Set i to 1.
3. Repeat this loop:
   1. If A[i] = x,
      1. exit the loop.
   2. Set i to i + 1.
4. Return i.

Việc thêm phần tử cầm canh giúp giảm bớt việc so sánh chỉ số hiện tại i với số các phần tử n ở mỗi vòng lặp. Tuy nhiên, điều này chỉ có thể được sử 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++:

#include <iostream>
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 " << result;
   return 0;
}

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

#include <stdio.h>

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:

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:

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(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
function search($arr, $x)
{
    $n = sizeof($arr);
    for($i = 0; $i < $n; $i++)
    {
        if($arr[$i] == $x)
            return $i;
    }

    return -1;
}

// Driver Code
$arr = array(2, 3, 4, 10, 40);
$x = 10;
$n = count($arr);

$result = search($arr, $x);
if($result == -1)
    echo "Element is not present in array";
else
    echo "Element is present at index ", $result;
?>

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

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

+ Thuật Toán Tìm Kiếm Nhị Phân

Thuật toán tìm kiếm nhị phân là một trong các thuật toán sắp xếp được sử dụng rất nhiều trong thực tế. Hãy cùng mình đi tìm hiểu thuật toán tìm kiếm này nhé.

Tìm kiếm là một phần không thể thiếu của mọi ứng dụng, website hay phần mềm. Tính năng tìm kiếm cho phép người sử dụng nhanh chóng truy vấn và tìm kiếm các bản ghi theo mong muốn. Và một công cụ tìm kiếm nổi tiếng nhất hàng ngày chúng ta vẫn thường sử dụng đó là Google search.

Bài viết ngày hôm nay Techacademy sẽ giới thiệu cho độc giả một thuật toán tìm kiếm tối ưu áp dụng đối với trường hợp dữ liệu số đã sắp xếp.

Phát biểu thuật toán tìm kiếm nhị phân(Binary search)

Cho một mảng đã sắp xếp arr[] có n phần tử, viết một hàm tìm kiếm trả về chỉ số của phần tử có giá trị x trong arr[].

Giải thuật đơn giản nhất cho bài toán này là sử dụng linear search(tìm kiếm tuyến tính). Tức là bạn sẽ phải đi qua từng phần tử của mảng để đối chiếu với x cần tìm. Thuật toán này trong trường hợp xấu nhất cho độ phức tạp là O(n). Mình cũng sẽ minh họa code của thuật toán này dưới đây.

Đây là code C/C++ sử dụng linear search.

// Code from https://techacademy.edu.vn
#include <stdio.h>

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

Đây là code minh họa sử dụng đệ quy dùng Java và C/C++. Ngoài ra, tôi sẽ áp dụng thêm giải thuật khử đệ quy với C/C++.

Code minh họa C/C++ sử dụng đệ quy

// Code from https://nguyenvanhieu.vn
#include <stdio.h>

// Hàm tìm kiếm nhị phân sử dụng giải thuật đệ quy
int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;

        // Nếu arr[mid] = x, trả về chỉ số và kết thúc
        if (arr[mid] == x)
            return mid;

        // Nếu arr[mid] > x, gọi đệ quy tìm kiếm bên trái
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);

        // Ngược lại, nếu arr[mid] < x, gọi đệ quy tìm kiếm bên phải
        return binarySearch(arr, mid + 1, r, x);
    }

    // Trong trường hợp không tìm thấy
    return -1;
}

int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;

    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1)
        printf("%d xuat hien tai chi so %d", x, result);
    else
        printf("%d xuat hien tai chi so %d", x, result);
    return 0;
}

Code minh họa sử dụng đệ quy Java

// Code from https://nguyenvanhieu.vn
class BinarySearch {
    int binarySearch(int arr[], int l, int r, int x)
    {
        if (r >= l) {
            int mid = l + (r - l) / 2;

            // Nếu arr[mid] = x, trả về chỉ số và kết thúc
            if (arr[mid] == x)
                return mid;

            // Nếu arr[mid] > x, gọi đệ quy tìm kiếm bên trái
            if (arr[mid] > x)
                return binarySearch(arr, l, mid - 1, x);

            // Ngược lại, nếu arr[mid] < x, gọi đệ quy tìm kiếm bên phải
            return binarySearch(arr, mid + 1, r, x);
        }

        // Trong trường hợp không tìm thấy
        return -1;
    }

    public static void main(String args[])
    {
        BinarySearch ob = new BinarySearch();
        int arr[] = { 2, 3, 4, 10, 40 };
        int n = arr.length;
        int x = 10;
        int result = ob.binarySearch(arr, 0, n - 1, x);
        if (result == -1)
            System.out.println("Không tìm thấy phần tử " + x);
        else
            System.out.println("Phần tử " + x + " được tìm thấy tại chỉ số " + result);
    }
}

Code khử đệ quy sử dụng C/C++

// Code from https://nguyenvanhieu.vn
#include <stdio.h>

// Hàm tìm kiếm nhị phân sử dụng giải thuật đệ quy
int binarySearch(int arr[], int n, int x)
{
    int r = n - 1; // chỉ số phần tử cuối
    int l = 0; // Chỉ số phần tử đầu tiên
    while (r >= l) {
        int mid = l + (r - l) / 2; // Tương đương (l+r)/2 nhưng ưu điểm tránh tràn số khi l,r lớn
        // Nếu arr[mid] = x, trả về chỉ số và kết thúc.  
        if (arr[mid] == x)
            return mid;
        // Nếu arr[mid] > x, cập nhật lại right
        if (arr[mid] > x)
            r = mid - 1;
        // Nếu arr[mid] < x, cập nhật lại left
        if (arr[mid] < x)
            l = mid + 1;
    }
    // Nếu không tìm thấy
    return -1;
}

int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, n, x);
    if (result == -1)
        printf("%d xuat hien tai chi so %d", x, result);
    else
        printf("%d xuat hien tai chi so %d", x, result);
    return 0;
}

+ Thuật Toán Tìm Kiếm Nội Suy

Thuật toán tìm kiếm nội suy là một sự cải tiến của tìm kiếm nhị phân Binary Search. Nó có xu hướng tiến gần đến vị trí, giá trị tìm kiếm. Do đó tốc độ tìm kiếm được tối ưu rất cao và nhanh hơn nhiều so với Binary Search.

Cách thức hoạt động của nó dựa trên Binary Search, nhưng có sự cải tiến hơn. Đó chính là nó tìm ra phần tử gần với giá trị tìm kiếm nhất và bắt đầu từ đó để tìm.

Ví dụ:

Chúng ta có danh sách các sinh viên trong một lớp. Nếu chúng ta muốn tìm một bạn tên Tiến, thì chúng ta sẽ ưu tiên việc tìm kiếm từ cuối danh sách. Chứ không nên tìm kiếm từ đầu danh sách vì điều đó rất mất thời gian.

Với Interpolation Search nó sẽ linh hoạt hơn rất nhiều trong lúc tìm kiếm

Giả sử chúng ta có:

Left, right là hai vị trí đầu và cuối.

T là tập.

X là giá trị cần tìm.

Giải thích thuật toán

Bước 1:Chúng ta sẽ sử dụng công thức tìm phần tử chính giữa của tập theo cách tìm kiếm Binary Search:

Search = left + (right - left) * 1/2

Trong công thức trên chúng ta sẽ thay giá trị 1/2 bằng biểu thức sau:

(X - T[left]) / (T[right] - T[left])

Sau khi thay biểu thức vào công thức sẽ được công thức mới như sau:

Search = left + (X- T[left]) * (right - left) / (T[right] - T[left])

Bước 2: Bây giờ chúng ta sẽ kiểm tra T[Search] nếu bằng X thì Search chính là vị trí cần tìm.

Nếu Search < X thì tăng left lên một đơn vị rồi quay lại bước 1.

Nếu Search > X thì giảm right xuống một đơn vị rồi quay lại bước 1.

Việc thêm phần tử cầm canh giúp giảm bớt việc so sánh chỉ số hiện tại i với số các phần tử n ở mỗi vòng lặp. Tuy nhiên, điều này chỉ có thể được sử 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++:

#include <iostream>
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 " << result;
   return 0;
}

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

#include <stdio.h>

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")