Các thuật toán tìm kiếm cơ bản: tìm kiếm tuần tự, tìm kiếm nhị phân

Tìm kiếm là một yêu cầu cơ bản và đã được nghiên cứu trong nhiều năm. Trong thực tế, có nhiều thuật toán tìm kiếm khác nhau được sử dụng cho từng bài toán cụ thể.

Có thể bạn quan tâm

Trong bài viết này, chúng ta sẽ tìm hiểu về hai thuật toán tìm kiếm cơ bản nhất: tìm kiếm tuần tự (sequential search) và tìm kiếm nhị phân (binary search). Chúng ta cũng sẽ xem xét các phương pháp tìm kiếm có sẵn trên các kiểu dữ liệu tập hợp trong ngôn ngữ lập trình C#.

Bạn đang xem: Các thuật toán tìm kiếm cơ bản: tìm kiếm tuần tự, tìm kiếm nhị phân

Contents

1 Thuật toán tìm kiếm tuần tự – Sequential Search
2 Tìm giá trị lớn nhất / nhỏ nhất
3 Thuật toán tìm kiếm nhị phân
4 Hỗ trợ tìm kiếm trong C
5 Kết luận

Thuật toán tìm kiếm tuần tự – Sequential Search

Tìm kiếm tuần tự (Sequential Search) là một thuật toán tìm kiếm đơn giản và tự nhiên mà ai cũng có thể nghĩ ra và dễ dàng cài đặt bằng mã code.

Trong tìm kiếm tuần tự, bạn bắt đầu từ đầu hoặc cuối của mảng dữ liệu và duyệt qua từng phần tử một. Trong quá trình duyệt, bạn so sánh giá trị cần tìm với giá trị của từng phần tử. Nếu tìm thấy phần tử có giá trị cần tìm, quá trình tìm kiếm dừng lại. Quá trình tìm kiếm cũng dừng lại nếu đã duyệt hết danh sách. Khi đó, giá trị cần tìm không có trong mảng dữ liệu.

Chúng ta thường gặp hai loại kết quả tìm kiếm. Loại thứ nhất chỉ trả lời câu hỏi “có giá trị này trong mảng hay không”. Loại thứ hai trả lời thêm cho câu hỏi “phần tử đó nằm ở vị trí nào”.

Do tìm kiếm tuần tự rất đơn giản, chúng ta không cần giải thích nhiều. Hãy thực hiện một ví dụ xây dựng các phương thức hỗ trợ tìm kiếm tuần tự.

Trong mã chương trình dưới đây, để giúp bạn xây dựng các phương thức tìm kiếm “thực tế”, chúng ta sử dụng một số kỹ thuật lập trình C# nâng cao. Các kỹ thuật này bao gồm lập trình generic, extension method, generic delegate.

Bạn hãy tạo một project thuộc loại ConsoleApp (.NET Framework hoặc .NET Core) và viết mã code cho Program.cs.

Dưới đây là đoạn mã hoàn chỉnh của chương trình (Program.cs):

using System;
using System.Collections.Generic;
using static System.Console;

namespace P01_SequentialSearch
{
    class Program
    {
        static void Main(string[] args)
        {
            Title = "SEQUENTIAL SEARCH";

            var data = new[] { 1, 3, 9, 2, 4, 5, 7, 6, 8 };
            Print(data);

            var value = 6;
            var found = data.Search(value);

            WriteLine($"Tìm kiếm giá trị {value} : {(found ? $"tìm thấy" : "không tìm thấy")}");

            ReadKey();
        }

        public static void Print(IEnumerable array)
        {
            ForegroundColor = ConsoleColor.Green;

            foreach (var i in array)
            {
                Write($"{i} ");
            }

            ResetColor();
            WriteLine();
        }
    }

    public static class SequentialSearch
    {
        public static bool Search(this IEnumerable data, T value) where T : IComparable
        {
            foreach (var i in data)
            {
                if (i.CompareTo(value) == 0)
                    return true;
            }

            return false;
        }
    }
}

Trong ví dụ trên, bạn xây dựng một lớp tĩnh SequentialSearch với hai phương thức tìm kiếm Search. Tất cả các phương thức này được xây dựng dưới dạng extension method cho interface IEnumerable.

Phương thức Search giúp xác định xem một giá trị có nằm trong danh sách hay không.

Tìm giá trị lớn nhất / nhỏ nhất

Một bài toán khác của tìm kiếm tuần tự là xác định giá trị nhỏ nhất/lớn nhất trong một danh sách (không được sắp xếp).

Xem thêm : Công thức lượng giác, bảng công thức lượng giác đầy đủ nhất

Thuật toán tìm giá trị lớn nhất tuần tự rất đơn giản:

Chọn phần tử đầu (hoặc cuối) của danh sách và coi giá trị của nó là lớn nhất. Gán giá trị này cho một biến tạm max.
Duyệt qua các phần tử còn lại. Nếu gặp phần tử nào có giá trị lớn hơn max, ta gán cho max giá trị đó.
Khi kết thúc duyệt mảng, giá trị lưu trong biến tạm max chính là giá trị lớn nhất của danh sách.

Thuật toán tìm giá trị nhỏ nhất cũng thực hiện tương tự.

Dưới đây là đoạn mã để cài đặt thuật toán trên:

public static T Min(this IList data) where T : IComparable
{
    var min = data[0];

    foreach (var i in data)
    {
        if (i.CompareTo(min) < 0)
            min = i;
    }

    return min;
}

public static T Max(this IList data) where T : IComparable
{
    var max = data[0];

    foreach (var i in data)
    {
        if (i.CompareTo(max) > 0)
            max = i;
    }

    return max;
}

Phương thức Min và Max đều có hai phiên bản tương tự như các phương thức tìm kiếm đã viết ở phần trước.

Bạn có thể sử dụng các phương thức trên trong mã code như sau:

//var min = SequentialSearch.Min(data);
//var max = SequentialSearch.Max(data);

var min = data.Min();
var max = data.Max();

WriteLine($"Giá trị nhỏ nhất: {min}");
WriteLine($"Giá trị lớn nhất: {max}");

Các thuật toán trên rất đơn giản và dễ hiểu, nhưng có độ phức tạp tính toán lớn trong trường hợp xấu nhất: O(n). Tuy nhiên, chúng phù hợp với dữ liệu không được sắp xếp.

Nếu dữ liệu đã được sắp xếp, bạn có thể sử dụng phương pháp tìm kiếm tốt hơn: tìm kiếm nhị phân (binary search).

Thuật toán tìm kiếm nhị phân

Tìm kiếm nhị phân (binary search) là một thuật toán tìm kiếm nhanh hơn rất nhiều so với tìm kiếm tuần tự, đặc biệt là trên danh sách lớn. Trong phần này, chúng ta sẽ tìm hiểu cách hoạt động của thuật toán này, sau đó sẽ trình bày cách cài đặt thuật toán bằng mã C#.

Giả sử chúng ta cần xác định xem giá trị 31 có nằm trong mảng [10, 14, 19, 26, 31, 33, 35, 42, 44] hay không.

Chúng ta thống nhất một số thuật ngữ như sau. Giá trị cần tìm được gọi là giá trị mục tiêu (target value). Chỉ số của phần tử đầu tiên trong mảng được gọi là chỉ số thấp (lower index), chỉ số của phần tử cuối cùng được gọi là chỉ số cao (upper index), và chỉ số của phần tử ở giữa dưới dạng trung vị (median index), trong đó median = (lower + upper) / 2. Giá trị của phần tử ở vị trí lower index được gọi là giá trị thấp (lower value). Tương tự, giá trị ở vị trí upper và median được gọi lần lượt là giá trị cao (upper value) và giá trị trung vị (median value).

Ban đầu, lower index = 0, lower value = 10, upper index = 9, upper value = 44. Ta dễ dàng tính được median index = 4 và median value = 27.

Binary Search

Thuật toán hoạt động như sau:

Xác định median index trong mảng ban đầu và so sánh median value với target value. Nếu bằng nhau, kết quả là tìm thấy. Nếu không, tiếp tục bước 2.
Nếu median value < target value, bỏ qua nửa mảng từ lower index đến median index, chỉ xem xét nửa còn lại từ median index + 1 đến upper. Nếu median value > target value, bỏ qua nửa mảng từ median index đến upper index.
Coi nửa mảng còn lại là mảng ban đầu và lặp lại bước 1.

Xem thêm : Bài 10 – Chương trình con trong ngôn ngữ lập trình Python

Quá trình trên lặp lại cho đến khi: (1) median value = target value; hoặc (2) mảng con không thể chia nhỏ hơn, tức là upper index <= lower index. Nếu đạt được điều kiện dừng mà không tìm thấy, kết quả là target value không có trong mảng.

Tìm kiếm nhị phân khó hiểu hơn tìm kiếm tuần tự, nhưng lại thực hiện nhanh hơn nhiều. Độ phức tạp của tìm kiếm nhị phân trong trường hợp xấu nhất là O(log n). Tuy nhiên, tìm kiếm nhị phân chỉ áp dụng được cho các danh sách đã được sắp xếp.

Thuật toán tìm kiếm nhị phân có hai cách cài đặt: sử dụng vòng lặp và sử dụng đệ quy. Việc sử dụng đệ quy giúp mã code gọn nhẹ và thể hiện rõ bản chất của giải pháp. Tuy nhiên, sử dụng đệ quy có vấn đề về hiệu suất khi sử dụng nhiều bộ nhớ cho quá trình đệ quy. Nói chung, hãy giải quyết bài toán mà không cần sử dụng đệ quy nếu có thể.

Dưới đây là đoạn mã hoàn chỉnh của chương trình (Program.cs):

using System;
using System.Collections.Generic;
using static System.Console;

namespace P02_BinarySearch
{
    class Program
    {
        static void Main(string[] args)
        {
            Title = "BINARY SEARCH";

            var data = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            Print(data);

            var value = 6;
            var found = data.Search(value);

            WriteLine($"Tìm kiếm giá trị {value} : {(found > -1 ? $"tìm thấy ở vị trí {found.ToString()}" : "không tìm thấy")}");

            ReadKey();
        }

        public static void Print(IEnumerable array)
        {
            ForegroundColor = ConsoleColor.Green;

            foreach (var i in array)
            {
                Write($"{i} ");
            }

            ResetColor();
            WriteLine();
        }
    }

    public static class BinarySearch
    {
        // sử dụng vòng lặp
        public static int Search(this IList data, T value) where T : IComparable
        {
            int upper = data.Count - 1, lower = 0, mid;

            while (lower <= upper)
            {
                mid = (upper + lower) / 2;

                if (data[mid].CompareTo(value) == 0)
                    return mid;
                else if (value.CompareTo(data[mid]) < 0)
                    upper = mid - 1;
                else
                    lower = mid + 1;
            }

            return -1; // không tìm thấy
        }

        // sử dụng đệ quy
        public static int SearchRecursive(this IList data, T value) where T : IComparable
        {
            int Recursive(int lower, int upper)
            {
                if (lower > upper)
                    return -1; // không tìm thấy
                else
                {
                    int mid = (upper + lower) / 2;

                    if (value.CompareTo(data[mid]) < 0)
                        return Recursive(lower, mid - 1);
                    else if (value.CompareTo(data[mid]) == 0)
                        return mid;
                    else
                        return Recursive(mid + 1, upper);
                }
            }

            return Recursive(0, data.Count - 1);
        }
    }
}

Trong đoạn mã trên, bạn cài đặt cả hai cách cài đặt của thuật toán tìm kiếm nhị phân: bằng vòng lặp và đệ quy.

Trong phiên bản đệ quy (SearchRecursive), mã sử dụng một tính năng mới tương đối của C#: hàm cục bộ (local function). Quá trình tìm kiếm đệ quy được thực hiện hoàn toàn bởi hàm cục bộ Recursive. Hàm bên ngoài (SearchRecursive) chỉ gọi hàm Recursive để lấy và trả về kết quả. Cách viết này giúp mã code gọn gàng hơn.

Hỗ trợ tìm kiếm trong C

Trên thực tế, khi làm việc với ngôn ngữ lập trình C#, bạn không cần tự viết các phương thức tìm kiếm riêng. Các kiểu dữ liệu và thư viện của C# hỗ trợ một số phương thức tìm kiếm khác nhau.

Hãy xem ví dụ sau:

using System;
using System.Collections.Generic;
using static System.Console;
using System.Linq;

namespace P03_SearchSupport
{
    class Program
    {
        static void Main(string[] args)
        {
            var data = new long[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            Print(data);

            long value = 6;

            var index0 = Array.BinarySearch(data, value);
            WriteLine($"Tìm kiếm giá trị {value} : {(index0 > -1 ? $"tìm thấy ở vị trí {index0.ToString()}" : "không tìm thấy")}");

            var index1 = Array.FindIndex(data, i => i == value);
            WriteLine($"Tìm kiếm giá trị {value} : {(index1 > -1 ? $"tìm thấy ở vị trí {index1.ToString()}" : "không tìm thấy")}");

            var index2 = data.ToList().IndexOf(value);
            WriteLine($"Tìm kiếm giá trị {value} : {(index2 > -1 ? $"tìm thấy ở vị trí {index2.ToString()}" : "không tìm thấy")}");

            data = new long[] { 1, 3, 9, 2, 4, 5, 7, 6, 8 };
            Print(data);

            var found = data.Contains(value);
            WriteLine($"Tìm kiếm giá trị {value} : {(found ? "tìm thấy" : "không tìm thấy")}");

            var min = data.Min();
            var max = data.Max();
            WriteLine($"Giá trị nhỏ nhất: {min}");
            WriteLine($"Giá trị lớn nhất: {max}");

            ReadKey();
        }

        public static void Print(IEnumerable array)
        {
            ForegroundColor = ConsoleColor.Green;

            foreach (var i in array)
            {
                Write($"{i} ");
            }

            ResetColor();
            WriteLine();
        }
    }
}

Như bạn thấy, có một số cách tìm kiếm trên các kiểu dữ liệu tập hợp trong C#:

Lớp Array hỗ trợ phương thức BinarySearch cài đặt sẵn thuật toán tìm kiếm nhị phân. Kết quả trả về của BinarySearch là chỉ số của phần tử (nếu tìm thấy) hoặc -1 (nếu không tìm thấy).

var index0 = Array.BinarySearch(data, value);

Phương thức FindIndex của lớp Array hỗ trợ tìm kiếm vị trí của phần tử với các điều kiện phức tạp hơn do người dùng tự cung cấp thông qua một hàm lambda.

var index1 = Array.FindIndex(data, i => i == value);

Kiểu List hỗ trợ phương thức IndexOf để xác định chỉ số của phần tử trong danh sách:

var index2 = data.ToList().IndexOf(value);

Thư viện LINQ cung cấp phương thức Contains giúp kiểm tra xem một giá trị có nằm trong danh sách hay không. Phương thức LINQ áp dụng được với hầu hết các kiểu dữ liệu tập hợp trong C#.

var found = data.Contains(value);

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu về hai thuật toán tìm kiếm cơ bản: tìm kiếm tuần tự và tìm kiếm nhị phân. Chúng ta cũng đã cài đặt chúng trong ngôn ngữ lập trình C#. Nhìn chung, các thuật toán này rất dễ cài đặt.

Ngoài ra, C# cũng hỗ trợ các phương thức tìm kiếm trên các kiểu dữ liệu tập hợp. Do đó, bạn không cần phải tự viết các phương thức tìm kiếm.

Nếu bạn thấy bài viết hữu ích, hãy chia sẻ nó để mọi người cùng tận hưởng. Nếu có thắc mắc hoặc muốn trao đổi thêm, hãy để lại bình luận bên dưới.

Cảm ơn bạn!

Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập