Các thuật toán tìm kiếm: tìm kiếm tuần tự, tìm kiếm nhị phân | Tự học ICT

Tìm kiếm là một trong những nhu yếu nền tảng và đã được nghiên cứu và điều tra 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 đơn cử .Trong bài học kinh nghiệm này tất cả chúng ta mở màn 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 pháp tìm kiếm được kiến thiết xây dựng sẵn trên các kiểu tài 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 kinh nghiệm riêng .

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 thuần nhất mà ai cũng nghĩ ra ngay và thuận tiện thiết lập 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 tài liệu và lần lượt duyệt qua từng thành phần. Trong quy trình duyệt, bạn so sánh giá trị cần tìm với giá trị của thành phần. Nếu tìm thấy thành phần có giá trị mình cần thì dừng quy trình tìm kiếm. Quá trình tìm cũng dừng lại nếu đã duyệt hết list. Khi này giá trị cần tìm không có trong mảng tài liệu .Chúng ta cũng thường gặp hai loại tác dụng tìm kiếm. Loại thứ nhất chỉ vấn đáp thắc mắc “ có giá trị này trong mảng hay không ”. Loại thứ hai vấn đáp thêm cho câu hỏi “ thành phần đó nằm ở vị trí nào ” .Do tìm kiếm tuần tự rất đơn thuần, tất cả chúng ta không cần mất nhiều công lý giải nữa. Hãy cùng triển khai một ví dụ thiết kế xây dựng các phương pháp tương hỗ 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 kiến thiết xây dựng các phương pháp tìm kiếm tương đối “ trong thực tiễn ”, 1 số ít kỹ thuật lập trình C # nâng cao được sử dụng. Các kỹ thuật này gồm có 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(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;
        }
        public static bool Search(this IEnumerable data, T value, Func equal)
        {
            foreach (var i in data)
            {
                if (equal(i, value)) return true;
            }
            return false;
        }
        public static int IndexOf(this IList 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(this IList data, T value, Func 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 hoặc IList.

Search giúp xác lập một giá trị có nằm trong list hay không. IndexOf giúp xác lập chỉ số của giá trị trong list .Overload thứ nhất của cả Search và IndexOf

public static bool Search(this IEnumerable data, T value) where T : IComparable
...
public static int IndexOf(this IList 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(this IEnumerable data, T value, Func equal)
...
public static int IndexOf(this IList data, T value, Func 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.

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

// 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 lập giá trị nhỏ nhất / lớn nhất trong một list ( 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 thuần :

1. 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.
2. 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ị đó.
3. 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 thi y hệt .Dưới đây là code thiết lập các 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 Min(this IList data, Func compare)
{
    var min = data[0];
    foreach (var i in data)
    {
        if (compare(i, 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;
}
public static T Max(this IList data, Func 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ựa như như các phương pháp tìm kiếm đã viết ở phần trước .Bạn sử dụng các phương pháp 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 tài liệu đã được sắp xếp, bạn hoàn toàn có thể sử dụng giải 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 quan trọng trên list lớn. Trong phần này tất cả chúng ta sẽ tìm hiểu và khám phá cách hoạt động giải trí của thuật toán này, sau đó sẽ trình diễn code C # setup cho thuật toán .Giả sử tất cả chúng ta cần xác lập 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 giải trí như sau :

1. 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.
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.
3. 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 hề phân loại được nữa, nghĩa là upper index < = lower index. Nếu đạt đến điều kiện kèm theo 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 setup : sử dụng vòng lặp và sử dụng đệ quy. Code sử dụng đệ quy gọn nhẹ và biểu lộ rõ thực chất của giải pháp. Tuy nhiên, nó có yếu tố về hiệu suất khi sử dụng nhiều bộ nhớ cho quy trình đệ quy. Nhìn chung, nếu hoàn toàn có thể hãy xử lý 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(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)
            {
                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(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 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 gồm có cả hai cách setup thuật toán sắp xếp nhị phân : lặp và đệ quy .Riêng so với phương pháp đệ 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ộ quy trình tìm kiếm đệ quy được thực thi bởi hàm cục bộ Recursive. Hàm chứa ( SearchRecursive ) trong thực tiễn chỉ gọi tới hàm Recursive để lấy và trả hiệu quả. Cách viết này giúp code ngăn nắp hơn .

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

Trên trong thực tiễn khi thao tác với C #, bạn không cần tự viết phương pháp tìm kiếm riêng. Các kiểu tài liệu và thư viện của C # tương hỗ một số ít phương pháp tìm kiếm khác nhau .Hãy cùng thực thi 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(IEnumerable array)
        {
            ForegroundColor = ConsoleColor.Green;
            foreach (var i in array)
            {
                Write($"{i}    ");
            }
            ResetColor();
            WriteLine();
        }
    }
}

Như bạn thấy, có 1 số ít cách tìm kiểu trên tài 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 tương hỗ tìm kiếm vị trí của thành phần với các điều kiện kèm theo phức tạp hơn do người dùng tự cung ứng trải qua một hàm lambda .

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

Kiểu List tương hỗ phương pháp IndexOf để xác lập chỉ số của thành phần trong list :

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

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

var found = data.Contains(value);

Kết luận

Trong bài học kinh nghiệm này tất cả 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ự thiết lập chúng trên C #. Nhìn chung, các thuật toán này rất dễ setup .Ngoài ra, C # cũng tương hỗ các phương pháp tìm kiếm trên các kiểu tài liệu tập hợp. Do vậy trên trong thực tiễn bạn không cần tự mình viết các phương pháp tìm kiếm .

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

Source: https://vietsofa.vn
Category : Góc học tập