thuật toán tìm kiếm nhanh nhất

Trong hầu hết các hệ quản lý dữ liệu, thao tác tìm kiếm thường được thực hiện nhất để khai thác thông tin khác nhau. Bởi vậy, khi xây dựng một hệ quản lý thông tin trên máy tính, bên cạnh các thuật toán tìm kiếm, các thuật toán sắp xếp dữ liệu cũng là một trong những chủ đề được quan tâm hàng đầu. Hãy cũng mình tìm hiểu về thuật toán tìm kiếm phổ biến nhé.

Thuật toán sắp xếp là gì?

Thuật toán sắp xếp Là bài toán giải quyết việc tổ chức dữ liệu theo một trật tự nhất định, thường là tăng dần hoặc giảm dần.

Ví dụ điển hình nhất trong thực tế như:

Các ứng dụng quản lý danh bạ ở điện thoại thì có sắp xếp theo số, theo tên. Quản lý học sinh thì có sắp xếp theo mã, điểm, theo lớp, theo trường, …

Như vậy, trong cuộc sống có rất nhiều mục đích cần phải sắp xếp các phần tử theo một trình tự nhất định. Như lúc bạn học lập trình bạn cần sắp xếp dãy số tăng dần, giảm dần bởi các kỹ thuật sắp xếp được nghiên cứu và phân tích kỹ lưỡng.

thuật toán sắp sếp là gì
thuật toán sắp sếp là gì

Trong ngành khoa học máy tính và toán học, thuật toán sắp xếp là một thuật toán sắp xếp các phần tử của một danh sách (hay một mảng) theo thứ tự tăng hoặc giảm tùy thuộc.

Có những thuật toán sắp sếp như:

  • Sắp xếp chọn
  • Sắp xếp chèn
  • Sắp xếp nổi bọt
  • Sắp xếp Quick sort
  • Sắp xếp Help sort
  • Sắp xếp Merge sort

Thuật toán tìm kiếm là gì?

Tìm kiếm là quá trình tìm một phần tử nằm trong một tập hợp rất nhiều phần tử dựa vào một yêu cầu nào đó. Ví dụ bạn cần tìm học sinh giỏi có tổng điểm cao nhất trong một danh sách học sinh của trường có 1000 học sinh thì quá trình đó ta gọi là tìm kiếm.

Nếu như một tập hợp đã được sắp xếp thì quá trình tìm kiếm trong tập hợp đó sẽ nhanh hơn.

Như ví dụ trên nếu điểm số học sinh đã được sắp xếp theo tăng dần hoặc giảm dần thì ta rất dễ tìm kiếm được học sinh đó. Còn nếu đó là một danh sách tùm lum không có thú tự thì bạn có thể sẽ mất nhiều thời gian để xử lý chúng.

thuật toán tìm kiếm là gì
thuật toán tìm kiếm là gì

Hiện nay, chúng ta thường sử dụng hai thuật toán tìm kiếm đó là

  • Thuật toán tìm kiếm tuyến tính.
  • Thuật toán tìm kiếm nhị phân.

Thuật toán tìm kiếm nhị phân là quá trình tìm kiếm trong một tập hợp đã được sắp xếp theo thứ tự.

Thuật toán tìm kiếm tuyến tính là quá trình tìm kiếm trong một tập hợp chưa sắp xếp.

Cả hai thuật toán đều có những ưu và nhược điểm khác nhau.

Xem thêm: Web dành cho lập trình viên

Thuật toán tìm kiếm tuyến tính

Ý tưởng

Thực hiện tìm kiếm từ đầu cho đến cuối mảng (hoặc ngược lại).

  • Nếu tìm thấy trả vị trí của kết quả tìm kiếm.
  • Nếu không tìm thấy thì trả về 1.

Các bước thực hiện

  • Bước 1: Duyệt mảng (n phần tử) từ vị trí đầu tiên i = 0.
  • Bước 2: Thực hiện so sánh giá trị arr[i] và key. Nếu arr[i] == key trả về vị trí i.
  • Bước 3: Nếu như duyệt hết phần tử mảng vẫn không tìm thấy thì trả về -1.

Đánh giá

  • Trong trường hợp tốt nhất, phần tử cần tìm nằm ngay ở vị trí đầu tiên, thuật toán sử dụng 1 lần so sánh.
  • Trong trường hợp xấu nhất, phần tử cần tìm nằm ngay ở vị trí cuối hoặc không nằm trong mảng, thuật toán cần sử dụng n-1 lần so sánh.
  • Linear Search đây là một giải thuật đơn giản khi hiện thực nó và giải thuật này khá hiệu quả với danh sách đủ nhỏ hoặc một danh sách chưa được sắp xếp.

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

Thuật toán tìm kiếm nhị phân là một thuật toán tìm kiếm nhanh so với thuật toán tìm kiếm tuần tự, nhất là đối với một danh sách lớn, nhiều phần tử.

Ý tưởng

Để triển khai được thuật toán này hãy chắc chắn là mảng đã được sắp xếp. Dưới đây là ý tưởng triển khai thuật toán.

Xét đoạn mảng arr[left…right] cần phần tử tìm kiếm phần tử x. Ta so sánh x với phần tử ở vị trí giữa của mảng(mid = (left + right)/2). Nếu:

  • Nếu phần tử arr[mid] = x. Đưa kết luận và thoát chương trình.
  • Nếu arr[mid] < x. Ta chỉ thực hiện tìm kiếm trên đoạn arr[mid+1…right].
  • Nếu arr[mid] > x. Ta chỉ thực hiện tìm kiếm trên đoạn arr[left…mid-1].

Khi áp dụng thuật toán tìm kiếm nhị phân. Độ phức tạp cho trường hợp xấu nhất gặp là O(log(n)).

Tại sao cần phải có thuật toán tìm kiếm?

Trong thực tế ở cuộc sống, có rất nhiều bài toán khác nhau. Nhưng hầu như tất cả những bài toán đó chúng ta đều quy về một bài toán duy nhất, đó chính là bài toán tìm kiếm.

Ví dụ đơn giản là khi bạn thực hiện giải một bài toán. Có thể bạn sẽ có nhiều cách thực hiện nó, nhưng mục đích cuối cùng của bạn chính là đi tìm lời giải của bài toán. Hay là khi bạn thực hiện một phép sắp xếp, lọc các phần tử của danh sách, mục đích chính của bạn đó là tìm kiếm những phần tử giúp thỏa mãn yêu cầu.

Dựa trên các nhu cầu thực tế, các bài toán tìm kiếm dẫn đến chúng ta cần tạo ra thuật toán tìm kiếm để giải quyết những vấn đề này.

Tùy vào cấu trúc dữ liệu mà chúng ta sẽ có những thuật toán tìm kiếm khác nhau sao cho phù hợp cho từng cấu trúc đó. Vì vậy, chúng ta không nên học thuộc lòng thuật toán tìm kiếm trên một tập dữ liệu duy nhất. Mà bạn hãy học ý tưởng của thuật toán và thực hiện áp dụng nó một cách linh hoạt cho các cấu trúc dữ liệu khác nhau ở các ngôn ngữ lập trình khác nhau. Từ đó lựa chọn được thuật toán nhanh nhất, tối ưu nhất cho mục đích của bạn.

Bài viết là những chia sẻ của mình về thuật toán tìm kiếm, cảm ơn các bạn đã quan tâm.

Bình luận