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 quan trọng và đã được nghiên cứu trong nhiều năm. Có rất 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ể.

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ự và tìm kiếm nhị phân. Chúng ta cũng sẽ xem xét các phương thức 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#.

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

Tìm kiếm tuần tự 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ử lần lượ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. Nếu duyệt hết danh sách mà không tìm thấy, 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 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".

Vì tìm kiếm tuần tự đơn giản, không cần giải thích chi tiết nữa. Hãy cùng xem một ví dụ về cách xây dựng các phương thức hỗ trợ tìm kiếm tuần tự.

Trong đoạn code dưới đây, để xây dựng các phương thức tìm kiếm tuần tự "thực tế", chúng ta sử dụng một số kỹ thuật lập trình C# nâng cao, bao gồm Lập trình generic, extension method và generic delegate. Hãy tạo một project ConsoleApp (NET Framework hoặc NET Core) và viết mã cho 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, chúng ta xây dựng lớp tĩnh SequentialSearch với phương thức Search. Phương thức này mở rộng từ IEnumerable và kiểu T phải implement giao diện IComparable.

Search giúp xác định 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 (chưa được sắp xếp).

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

1. Chọn phần tử đầu tiên (hoặc cuối cùng) của danh sách và xem giá trị đó là lớn nhất tạm. Gán giá trị này cho biến tạm max.
2. Duyệt qua từng phần tử còn lại. Nếu gặp phần tử nào có giá trị lớn hơn max, thay thế max bằng giá trị đó.
3. Khi kết thúc duyệt danh sách, 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 tương tự.

Dưới đây là đoạn mã cài đặt 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 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 chức năng tương tự như các phương thức tìm kiếm đã được viết trước đó.

Bạn có thể sử dụng các phương thức trên với các kiểu dữ liệu tập hợp thường gặp như mảng hoặc danh sách:

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

Các thuật toán trên đơn giản và dễ hiểu, nhưng độ phức tạp tính toán lớn: O(n) trong trường hợp xấu nhất. Tuy nhiên, chúng phù hợp với dữ liệu chưa đượ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.

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

Tìm kiếm nhị phân 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 trên các 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 và cài đặt code C# cho thuật toán.

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

Chúng ta sẽ sử dụng một số thuật ngữ 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 được gọi là lower value.
• Giá trị của phần tử ở vị trí upper index được gọi là upper value.
• Giá trị của phần tử ở vị trí median index được gọi là median value.

Ban đầu, lower index = 0, lower value = 10, upper index = 9, upper value = 44. Khi tính toán, ta có median index = 4 và median value = 27.

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

1. Xác định median index trong mảng gốc 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.
2. Nếu median value < target value, chỉ xem xét nửa mảng từ lower index đến median index + 1. Nếu median value > target value, chỉ xem xét nửa mảng từ median index đến upper index.
3. Lặp lại quá trình với nửa mảng còn lại.

Quá trình này lặp lại cho đến khi:

• median value = target value hoặc
• mảng con không thể chia được nữa, tức là upper index <= lower index. Nếu không tìm thấy, target không có trong mảng.

Tìm kiếm nhị phân khó hiểu hơn, nhưng cài đặt nhanh hơn nhiều so với tìm kiếm tuần tự, đặc biệt là với các danh sách 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 nhị phân chỉ áp dụng được với 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. Mã 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. Nếu có thể, hãy giải quyết bài toán mà không sử dụng đệ quy.

Dưới đây là đoạn mã đầy đủ 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);          }      }  }

Mã trên bao gồm cả hai cách cài đặt thuật toán tìm kiếm nhị phân: sử dụng vòng lặp và sử dụng đệ quy.

Đối với phương thức đệ quy (SearchRecursive), chúng ta sử dụng một tính năng 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 bao (SearchRecursive) thực chất chỉ gọi hàm Recursive để lấy và trả kết quả. Cách viết này giúp làm mã gọn gàng hơn.

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

Trong thực tế làm việc với C#, bạn không cần 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# hỗ trợ một số phương thức tìm kiếm khác nhau.

Hãy xem ví dụ dưới đây:

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ó sẵn để thực hiệ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 do người dùng chỉ định thông qua 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 để 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 cho 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, hai 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. Vì vậy, trong thực tế, bạn không cần phải viết các phương thức tìm kiếm riêng.

Nếu bạn thấy trang web hữu ích, hãy giúp đỡ trang web bằng cách thực hiện một hành động nhỏ để nâng cao sự phát triển và cung cấp dịch vụ tốt hơn.

Nếu bạn thấy bài viết hữu ích, hãy chia sẻ với mọi người.

Nếu bạn có bất kỳ câu hỏi hoặc cần trao đổi thêm, hãy viết trong phần thảo luận cuối trang.

Cảm ơn bạn!