Tìm kiếm trong lập trình

Để đọc hiểu bài này, bạn phải đọc 2 bài trước nó gồm :
- Lập trình Generic với C#.
- Sắp xếp.

Bên cạnh thao tác sắp xếp, ta cũng có một số thao tác cũng rất hay gặp khi lập trình liên quan đến tìm kiếm, ví dụ :
- Tìm kiếm một phần tử trong một danh sách chưa sắp xếp.
- Tìm kiếm một phần tử trong một danh sách đã dc sắp xếp rồi (giải thuật phổ biến nhất là BinarySearch).
- Insert một phần tử vào một danh sách đang dc sắp xếp rồi mà vẫn đảm bảo tính sắp xếp của danh sách đó (thường dùng BinarySearch để xác định ví trí để insert trc, rồi mới insert).
- Xác định vị trí cần thiết trong một danh sách đã sắp xếp để insert một phần tử mới vào (cũng dùng BinarySearch).

Bài viết này tôi sẽ giới thiệu một số hàm dc viết theo kiểu Generic Function, với tính tái sử dụng rất cao, performance tốt, có thể được sử dụng trong nhiều dự án C# khác nhau. Trừ khi yêu cầu của bạn rất đặc thù, còn không thì >95%, bạn có thể sử dụng nó mỗi khi gặp những vấn để nói trên. Trong bài viết này, tôi sẽ gửi kèm theo file.cs này, vì có rất nhiều thủ tục, bạn có thể sử dụng nó như là thư viện cho dự án của mình. Một số trường hợp còn thiếu (ex : tìm kiếm sử dụng IComparer), bạn có thể bổ sung, bằng cách viết tương tự, rất đơn giản.
Đầu tiên, thì cũng như thao tác Sort, BinarySearch cũng đã dc .Net cung cấp sẵn, tuy nhiên rất tiếc là nó có một hạn chế rất lớn, và tớ hầu như ko sử dụng hàm đó của .Net, và tự viết lấy theo Generic Function.
Nhược điểm của BinarySearch của .Net.
Giao diện hàm đó như sau (xem phần definition của List hoặc Array) :

public class List<T>{
  int BinarySearch(T item);
}

Giả sử bạn có một danh sách Person{int id, string name}. Nếu bạn muốn tìm tên của người có id = 10 thì sao. Với hàm BS này, bạn phải truyền vào một đối tượng Person có id=10, và name=null(cái ji cũng dc :D, vì thao tác so sánh thực hiện trên id) => performance ko tốt do phải new Person.

Vậy nếu tôi chỉ muốn truyền vào id thôi, ko new một Person nữa có dc ko? OK với những hàm được giới thiệu sau đây.
Nếu danh sách Person là một List thì như sau :

public static int searchOnSorted<E, K>(IList<E> list, K key) where E : IComparable<K>
{
  if (list == null) return CommonConstant.UNFOUND;

  int mid = 0,
      head = 0,
      tail = list.Count - 1;
  while (head <= tail) {
      mid = (head + tail) >> 1;
      int cmp = list[mid].CompareTo(key);
      if (cmp > 0) {
          tail = mid - 1;
      } else if (cmp < 0) {
          head = mid + 1;
      } else {
          return mid;
      }
  }
  return CommonConstant.UNFOUND;
} // end of BinarySearch

Nếu danh sách Person là một Person[] thì như sau :

public static int searchOnSorted<E, K>(E[] array, K key) where E : IComparable<K>
{
  if (array == null) return CommonConstant.UNFOUND;

  int mid = 0,
      head = 0,
      tail = array.Length - 1;
  while (head <= tail) {
      mid = (head + tail) >> 1;
      int cmp = array[mid].CompareTo(key);
      if (cmp > 0) {
          tail = mid - 1;
      } else if (cmp < 0) {
          head = mid + 1;
      } else {
          return mid;
      }
  }
  return CommonConstant.UNFOUND;
} // end of BinarySearch

Để có thể sử dụng dc hàm này, bạn cần chỉnh lớp Person một chút như sau, bắt nó implement IComparable như sau :

public class Person : IComparable<Person>, IComparable<int>
{
  public int id;
  public string name;
  public Person(int inNo, string inName)
  {
      id = inNo;
      name = inName;
  }

  #region IComparable Members
  public int CompareTo(Person other)