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

Đăng bởi

23/11/2019

Hướng dẫn tự học cấu trúc dữ liệu và giải thuật với C# 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 trong những yêu cầu nền tảng và đã được nghiên cứu qua nhiều năm. Có rất nhiều thuật toán tìm kiếm khác nhau được sử dụng trong từng bài toán cụ thể.

Trong bài học này chúng ta bắt đầu bằng hai loại 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 thức tìm kiếm được xây dựng sẵn trên các kiểu dữ liệu tập hợp của C#.

Một số thuật toán tìm kiếm nâng cao sẽ được xem xét trong những bài học riêng.

NỘI DUNG CỦA BÀI Ẩn

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à thuật toán tìm kiếm “tự nhiên” và đơn giản nhất mà ai cũng nghĩ ra ngay và dễ dàng cài đặt bằng code.

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

Chúng ta cũng 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 mất nhiều công giải thích nữa. Hãy cùng thực hiện một ví dụ xây dựng các phương thức hỗ trợ tìm kiếm theo kiểu tuần tự.

Trong code chương trình dưới đây, để giúp các bạn xây dựng các phương thức tìm kiếm tương đối “thực tế”, một số kỹ thuật lập trình C# nâng cao được sử dụng. 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 code cho Program.cs.

Dưới đây là full code 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 = SequentialSearch.Search(data, value);
            //var found = SequentialSearch.Search(data, value, (a, b) => a == b);
            //var found = data.Search(value, (a, b) => a == b);
            var found = data.Search(value);
            //var index = SequentialSearch.IndexOf(data, value);
            //var index = SequentialSearch.IndexOf(data, value, (a, b) => a == b);
            //var index = data.IndexOf(value, (a, b) => a == b);
            var index = data.IndexOf(value);
            WriteLine($"Searching for {value} : {(found ? $"found at {index.ToString()}" : "not found")}");
            
            ReadKey();
        }
        public static void Print<T>(IEnumerable<T> array)
        {
            ForegroundColor = ConsoleColor.Green;
            foreach (var i in array)
            {
                Write($"{i}    ");
            }
            ResetColor();
            WriteLine();
        }
    }
    public static class SequentialSearch
    {
        public static bool Search<T>(this IEnumerable<T> data, T value) where T : IComparable
        {
            foreach (var i in data)
            {
                if (i.CompareTo(value) == 0) return true;
            }
            return false;
        }
        public static bool Search<T>(this IEnumerable<T> data, T value, Func<T, T, bool> equal)
        {
            foreach (var i in data)
            {
                if (equal(i, value)) return true;
            }
            return false;
        }
        public static int IndexOf<T>(this IList<T> data, T value) where T : IComparable
        {
            for (var i = 0; i < data.Count; i++)
            {
                if (data[i].CompareTo(value) == 0) return i;
            }
            return -1; // không tìm thấy
        }
        public static int IndexOf<T>(this IList<T> data, T value, Func<T, T, bool> equal)
        {
            for (var i = 0; i < data.Count; i++)
            {
                if (equal(data[i], value)) return i;
            }
            return -1; // không tìm thấy
        }
    }
}

Trong ví dụ trên bạn xây dựng static class SequentialSearch với các phương thức Search (2 overload) và IndexOf (2 overload). Tất cả các phương thức này đều xây dựng ở dạng extension method cho interface IEnumerable<T> hoặc IList<T>.

Search giúp xác định một giá trị có nằm trong danh sách hay không. IndexOf giúp xác định chỉ số của giá trị trong danh sách.

Overload thứ nhất của cả Search và IndexOf

public static bool Search<T>(this IEnumerable<T> data, T value) where T : IComparable
...
public static int IndexOf<T>(this IList<T> data, T value) where T : IComparable
...

có thể làm việc với bất kỳ kiểu dữ liệu nào thực thi giao diện IComparable. Bất kỳ class nào thực thi IComparable đều có phương thức CompareTo giúp so sánh giá trị của các object của class.

Overload thứ hai của Search và IndexOf

public static bool Search<T>(this IEnumerable<T> data, T value, Func<T, T, bool> equal)
...
public static int IndexOf<T>(this IList<T> data, T value, Func<T, T, bool> equal)
...

Không đặt ra yêu cầu với kiểu dữ liệu của phần tử nhưng đòi hỏi phải cung cấp phương pháp so sánh giá trị của các phần tử thông qua generic delegate Func<T, T, bool>.

Với các phương thức xây dựng như trên bạn có thể sử dụng chúng với các kiểu dữ liệu tập hợp quen thuộc như mảng hay danh sách:

// gọi theo kiểu static method
//var found = SequentialSearch.Search(data, value);
//var found = SequentialSearch.Search(data, value, (a, b) => a == b);
// gọi theo kiểu extension method
//var found = data.Search(value, (a, b) => a == b);
var found = data.Search(value);
// gọi theo kiểu static method
//var index = SequentialSearch.IndexOf(data, value);
//var index = SequentialSearch.IndexOf(data, value, (a, b) => a == b);
// gọi theo kiểu extension method
//var index = data.IndexOf(value, (a, b) => a == b);
var index = data.IndexOf(value);

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 sắp xếp).

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

Chọn phần tử ở đầu (hoặc cuối) danh sách và tạm 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.
Lần lượt 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 thì cho max nhận luôn 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 y hệt.

Dưới đây là code cài đặt các thuật toán trên:

public static T Min<T>(this IList<T> 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 Min<T>(this IList<T> data, Func<T, T, int> compare)
{
    var min = data[0];
    foreach (var i in data)
    {
        if (compare(i, min) < 0)
            min = i;
    }
    return min;
}
public static T Max<T>(this IList<T> data) where T : IComparable
{
    var max = data[0];
    foreach (var i in data)
    {
        if (i.CompareTo(max) > 0)
            max = i;
    }
    return max;
}
public static T Max<T>(this IList<T> data, Func<T, T, int> compare)
{
    var max = data[0];
    foreach (var i in data)
    {
        if (compare(i, max) > 0)
            max = i;
    }
    return max;
}

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

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

//var min = SequentialSearch.Min(data);
//var min = SequentialSearch.Min(data, (a, b) => a.CompareTo(b));
var min = data.Min();
WriteLine($"Min value: {min}");
//var max = SequentialSearch.Max(data);
//var max = SequentialSearch.Max(data, (a, b) => a.CompareTo(b));
var max = data.Max();            
WriteLine($"Max value: {max}");

Các thuật toán trên mặc dù rất đơn giản, dễ hiểu, dễ cài đặt nhưng lại có độ phức tạp tính toán lớn: O(n) trong trường hợp xấu nhất. Tuy nhiên nó 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ểu kiểu 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 rất nhanh nếu so với tìm kiếm tuần tự, đặc biệt 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 code C# cài đặt cho thuật toán.

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ố cách gọi như sau. Giá trị cần tìm được gọi là target value. Chỉ số phần tử đầu tiên của mảng được gọi là Lower index, chỉ số phần tử cuối cùng được gọi là Upper index, chỉ số của phần tử ở giữa được gọi là Median index, trong đó Median = (Lower + Upper)/2. Giá trị của phần tử ở vị trí Lower index sẽ được gọi là Lower value. Tương tự như vậy, giá trị ở vị trí Upper và Median sẽ được gọi là Upper value và Median value.

Ban đầu, lower index = 0, lower value = 10, upper index = 9, upper value = 44. Dễ dàng tính ra Median index = 4 và Median value = 27.

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

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

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

Tìm kiếm nhị phân khó hiểu hơn nhưng lại thực hiện nhanh hơn nhiều so với tìm kiếm tuần tự, nhất là trong những danh sách kích thước lớn. Độ 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 kiểu nhị phân chỉ áp dụng được với những 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. Code sử dụng đệ quy gọn nhẹ và thể hiện rõ bản chất của giải pháp. Tuy nhiên, nó có vấn đề về hiệu suất khi sử dụng nhiều bộ nhớ cho quá trình đệ quy. Nhìn chung, nếu có thể hãy giải quyết bài toán không dùng đến đệ quy.

Dưới đây là full code 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);
            var found = data.SearchRecursive(value);
            WriteLine($"Searching for {value} : {(found > -1 ? $"found at {found.ToString()}" : "not found")}");
            ReadKey();
        }
        public static void Print<T>(IEnumerable<T> 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<T>(this IList<T> data, T value) where T : IComparable
        {
            int upper = data.Count - 1, lower = 0, mid;
            while (lower <= upper)
            {
                med = (upper + lower) / 2;
                if (data[med].CompareTo(value) == 0) return med;
                else if (value.CompareTo(data[med]) < 0)
                    upper = med - 1;
                else
                    lower = med + 1;
            }
            return -1; // không tìm thấy
        }
        // sử dụng đệ quy
        public static int SearchRecursive<T>(this IList<T> 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 med = (upper + lower) / 2;
                    if (value.CompareTo(data[med]) < 0)
                        return Recursive(lower, med - 1);
                    else if (value.CompareTo(data[med]) == 0)
                        return med;
                    else
                        return Recursive(med + 1, upper);
                }
            }     
 
            return Recursive(0, data.Count - 1);
        }
    }
}

Code ở trên bao gồm cả hai cách cài đặt thuật toán sắp xếp nhị phân: lặp và đệ quy.

Riêng đối với phương thức đệ quy (SearchRecursive), trong code có sử dụng một tính năng tương đối mới của C#: hàm cục bộ (local function). Toàn bộ quá trình tìm kiếm đệ quy được thực hiện bởi hàm cục bộ Recursive. Hàm chứa (SearchRecursive) thực tế chỉ gọi tới hàm Recursive để lấy và trả kết quả. Cách viết này giúp 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 C#, bạn không cần tự viết 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 cùng thực hiện 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($"Searching for {value} : {(index0 > -1 ? $"found at {index0.ToString()}" : "not found")}");
            var index1 = Array.FindIndex(data, i => i == value);
            WriteLine($"Searching for {value} : {(index1 > -1 ? $"found at {index1.ToString()}" : "not found")}");
            var index2 = data.ToList().IndexOf(value);
            WriteLine($"Searching for {value} : {(index2 > -1 ? $"found at {index2.ToString()}" : "not found")}");
            data = new long[] { 1, 3, 9, 2, 4, 5, 7, 6, 8 };
            Print(data);
            var found = data.Contains(value);
            WriteLine($"Searching for {value} : {(found ? "found" : "not found")}");
            var min = data.Min();
            var max = data.Max();
            WriteLine($"Min value: {min}");
            WriteLine($"Max value: {max}");
            ReadKey();
        }
        public static void Print<T>(IEnumerable<T> 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ểu trên 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 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);

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 học này chúng ta đã cùng xem xét 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 đã tự cài đặt chúng trên 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 vậy trên thực tế bạn không cần tự mình viết các phương thức tìm kiếm.

[wpdm_package id=’11827′]

+ Nếu bạn thấy site hữu ích, trước khi rời đi hãy giúp đỡ site bằng một hành động nhỏ để site có thể phát triển và phục vụ bạn tốt hơn.
+ Nếu bạn thấy bài viết hữu ích, hãy giúp chia sẻ tới mọi người.
+ Nếu có thắc mắc hoặc cần trao đổi thêm, mời bạn viết trong phần thảo luận cuối trang.
Cảm ơn bạn!

Previous Lesson

Back to Tutorial

Theo dõi

2 Thảo luận

Cũ nhất

Mới nhất

Phản hồi nội tuyến

Xem tất cả bình luận

khoa

28/04/2020 11:05

khi nào mới ra bài Tree vậy ad?

Trả lời

EMIN3M

20/06/2020 11:02

Nhiều bài giảng rất dễ hiểu nhưng bài viết này code có vẻ hơi phức tạp hơn mức cần thiết. Dù sao cũng chỉ là thuật toán search đơn giản thôi mà?

Xây dựng ứng dụng quản lý với Radzen Blazor

Quy trình làm việc với Radzen Blazor

Radzen Blazor – Công cụ phát triển nhanh ứng dụng quản…

C# 9.0 có gì mới?

Sử dụng git ignore ở chế độ offline

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

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

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

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

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

Kết luận

Bài mới

Thực hành lập trình với giao thức mạng

Giao thức Tcp

Giao thức Udp

Thực hành cài đặt phần mềm mạng (2) – FTP

Thực hành cài đặt phần mềm mạng (1) – web server

BÀI VIẾT PHỔ BIẾN

Hạn chế sử dụng boxing/unboxing – C# best practices

Console MVC Library cho .NET (1): giới thiệu chung

Xây dựng ứng dụng quản lý với Radzen Blazor

Liên kết bạn bè

CHUYÊN MỤC PHỔ BIẾN