Hôm nay, HopLongTech sẽ giới thiệu về năm thuật toán tìm kiếm cùng với việc triển khai chúng trong C ++ và Java. – Thuật toán Linear Search
– Thuật toán Binary Search
– Thuật toán Ternary Search
– Thuật toán Jump Search
– Thuật toán Exponential Search 1. Thuật toán Linear Search
Đây là thuật toán đơn giản nhất trong tất cả các thuật toán tìm kiếm. Trong kiểu tìm kiếm này, một hoạt động tìm kiếm liên tiếp được diễn ra qua tất cả từng phần tử. Mỗi phần tử đều được kiểm tra và nếu tìm thấy bất kỳ kết nối nào thì phần tử cụ thể đó được trả về; nếu không tìm thấy thì quá trình tìm kiếm tiếp tục diễn ra cho tới khi tìm kiếm hết dữ liệu.
– Độ phức tạp về thời gian: O
– Độ phức tạp không gian: O (1)
Dưới đây là một ví dụ việc triển khai tìm kiếm tuyến tính trong C ++2. Thuật toán Binary Search
Binary Search – tìm kiếm nhị phân, còn gọi là tìm kiếm nửa khoảng, tìm kiếm logarit, hay binary chop, là một thuật toán tìm kiếm xác định vị trí của một giá trị cần tìm trong một mảng đã được sắp xếp. Thuật toán tiến hành so sánh giá trị cần tìm với phần tử đứng giữa mảng.
– Độ phức tạp thời gian: O (log [n]) trong đó cơ số của log = 2
– Độ phức tạp của không gian: O (1) để thực hiện lặp trong khi O (log [n]) để thực hiện đệ quy vì với mỗi lần gọi đệ quy, một ngăn xếp mới được tạo ra.
Dưới đây là cách triển khai đệ quy của tìm kiếm nhị phân trong Java. Để thực hành, hãy cố gắng tự viết bản triển khai lặp đi lặp lại. Ví dụ:3. Thuật toán Ternary Search
Tương tự với thuật toán tìm kiếm nhị phân, Ternary Search – Tìm kiếm tam phân là một kỹ thuật trong khoa học máy tính dùng để tìm kiếm giá trị lớn nhất (maximum) hay nhỏ nhất (minimum) của một unimodal function, và đây cũng là một ví dụ ứng dụng lớp thuật toán Chia để trị (divide and conquer).
– Độ phức tạp thời gian: O (log [n]) trong đó cơ số của log = 3
– Độ phức tạp của không gian: O (1) để thực hiện lặp lại trong khi O (log [n]) để thực hiện đệ quy4. Thuật toán Jump Search
Cơ chế của Jump Search đó là tìm ra một hệ số nhảy được tính bằng : Căn bậc hai của số phần tử. Từ hệ số tìm được, Jump Search sẽ thực hiện nhảy phần tử theo hệ số để tìm ra phần từ lớn hơn giá trị tìm kiếm. => Phần tử tìm kiếm sẽ nằm trong khoảng của nhảy mà chứa phần từ lớn hơn giá trị tìm kiếm ở trên.
– Độ phức tạp về thời gian: O (log [sqrt (n)])
– Độ phức tạp của không gian: O (1) để triển khai lặp lại trong khi O (log [sqrt (n)]) để triển khai đệ quyVí dụ: 5. Thuật toán Exponential Search
Exponential Search là một cải tiến so với tìm kiếm nhị phân. Nó hoạt động trên một mảng được sắp xếp nhất định. Thay vì thực hiện tìm kiếm nhị phân trên toàn bộ tập dữ liệu, chúng ta tìm một khối có giá trị đích và sau đó thực hiện tìm kiếm nhị phân trong khối nhỏ đó. Để tìm khối, chúng ta lấy chỉ số (1) và kiểm tra giá trị của nó với giá trị đích. Nếu mục tiêu nhiều hơn giá trị chỉ mục này, thì chúng ta nhân đôi độ dài của khối hiện tại và kiểm tra chỉ mục (2) và tiếp tục làm điều này cho chỉ mục (4), (8), (16), v.v. cho đến khi tìm ra khối thích hợp. Vì toàn bộ hoạt động của khối này xảy ra trong 1–2–4–8–16-…, đó là lý do tìm kiếm này được gọi là tìm kiếm theo cấp số nhân.
– Độ phức tạp về thời gian: O (log [i]) trong đó i là chỉ số của phần tử cần tìm kiếm
– Độ phức tạp không gian: O (1) khi chúng ta sử dụng lặp đi lặp lại tìm kiếm nhị phân trong khi O (log [i]) để thực hiện đệ quy tìm kiếm nhị phân.Ví dụ: 5 thuật toán này không phải là những thuật toán tìm kiếm duy nhất hiện có. Còn một số thuật toán tìm kiếm phố biển khác như Tìm kiếm Nội suy hay Tìm kiếm Fibbonaci. Nhưng nếu bạn chú ý quan sát, bạn sẽ nhận ra tìm kiếm bậc ba, bước nhảy và hàm mũ chẳng qua là một bản sửa đổi của tìm kiếm tuyến tính hoặc nhị phân. Và trường hợp của phép nội suy và tìm kiếm fibonacci cũng vậy. Do đó, nếu bạn thành thạo với tìm kiếm tuyến tính và nhị phân, bạn sẽ dễ dàng nắm bắt được bất kỳ thuật toán tìm kiếm nào trong số này. | 
