Các thuật toán tìm kiếm trong C, C++ thường gặp

Thuật toán tìm kiếm trong C, C++ là một bài học “vỡ lòng” cần phải nắm dành cho những người vừa bước chân vào thế giới lập trình. Trong bài viết này, TopBranding.vn sẽ khái quát cho bạn các thuật toán tìm kiếm trong C, C++ thường gặp. 

Các thuật toán tìm kiếm thường gặp

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

Thuật toán tìm kiếm là thuật toán dùng để tìm kiếm phần tử trong một danh sách cho trước theo một tiêu chí nhất định.

II. Các thuật toán tìm kiếm trong C, C++

1. Binary search (Tìm kiếm nhị phân)

a. Đặc trưngThụât toán tìm kiếm nhị phân (Binary Search) hay còn được gọi là tìm kiếm một nửa là thụât toán được sử dụng rất nhiều trong thực tế cho phép tìm kiếm vị trí của một phần tử trong một mảng đã được sắp xếp.

Dãy đã được sắp xếp từ thấp đến cao

b. Cách thức hoạt độngThụât toán tìm kiếm nhị phân thực hiện tìm kiếm một mảng đã sắp xếp bằng cách liên tục chia các khoảng tìm kiếm thành 1 nửa. Bắt đầu với một khoảng từ phần tử đầu mảng tới cuối mảng. 

Nếu giá trị của phần tử cần tìm nhỏ hơn giá trị của phần từ nằm ở giữa khoảng thì thu hẹp phạm vi tìm kiếm từ đầu mảng tới giữa mảng và ngược lại. Cứ thế tiếp tục chia phạm vi thành các nửa cho dến khi tìm thấy hoặc đã duyệt hết.

Số cần tìm là 6

Trong ví dụ trên số cần tìm là 6. Mảng đã được sắp xếp từ cao đến thấp, bao gồm 7 phần tử nên chọn phần tử chính giữa để chia đôi dãy. Vì số cần tìm lớn hơn số ở giữa (6>4) nên thu hẹp phạm vi từ đầu đến số 4. Chúng ta lại tiếp tục chia dãy đó ra làm 2 và dùng cách tương tự để tìm ra số cần tìm. 

c. Cách dùng 

Tham khảo Link.

Code tìm kiếm nhị phân

2. Linear search (Tìm kiếm tuyến tính)

a. Đặc trưng

Đây là một giải thuật khá đơn giản để thực hiện, nó rất phù hợp khi cần tìm kiếm trên một danh sách vừa đủ và chưa được sắp xếp. Trong trường hợp cần tìm kiếm với một danh sách lớn hoặc nhiều lần chúng ta nên tìm một giải thuật khác hiệu quả hơn.

Tìm kiếm trên một danh sách vừa đủ và không sắp xếp

b. Cách thức hoạt động

Thuật toán tìm kiếm tuyến tính là phương pháp tìm kiếm một phần tử cho trước trong một danh sách bằng cách duyệt lần lượt từng phần từ của danh sách đó đến khi nào tìm được giá trị mong muốn hay đã duyệt hết qua hết danh sách.

Duyệt lần lượt trong danh sách đến khi tìm thấy phần tử cần tìm

c. Cách dùng  

Tham khảo Link. 

Code tìm kiếm tuyến tính

3. Interpolation search (Tìm kiếm nội suy)

a. Đặc trưng

Thuật toán tìm kiếm nội suy được cải tiến dựa trên tìm kiếm nhị phân Binary Search. Nó có xu hướng tiến gần đến vị trí, giá trị tìm kiếm.

b. Cách thức hoạt động

Nó sẽ tìm ra phần tử gần với giá trị tìm kiếm nhất và bắt đầu từ đó để tìm. Do đó tốc độ tìm kiếm được tối ưu và nhanh hơn nhiều so với Binary Search.

Bắt đầu tìm từ phần tử gần với giá trị tìm kiếm 

Ví dụ: Bạn cần tìm số 2 trong một bảng danh sách trên thì bạn sẽ khoanh vùng tìm kiếm từ các phần tử gần với 2 như 1; 3 rồi mới bắt đầu tìm. 

c. Cách dùng Tham khảo Link.

Code tìm kiếm nội suy

Trên đây là các thuật toán trong C, C++ thường gặp. Hi vọng bài viết này sẽ giúp bạn có cái nhìn tổng quan về thuật toán này. Nếu còn bất kì thắc mắc nào, hãy để lại bình luận bên dưới và đừng quên chia sẻ bài viết nếu bạn thấy có ích nhé!