Thuật toán tìm kiếm là một khái niệm khoa học máy tính cơ bản mà bạn nên hiểu với tư cách là nhà phát triển. Chúng hoạt động bằng cách sử dụng phương pháp từng bước để định vị dữ liệu cụ thể trong tập hợp dữ liệu
Trong bài viết này, chúng ta sẽ tìm hiểu cách các thuật toán tìm kiếm hoạt động bằng cách xem xét cách triển khai của chúng trong Java và Python
Thuật toán tìm kiếm là gì?
Theo Wikipedia, một thuật toán tìm kiếm là
Bất kỳ thuật toán nào giải quyết vấn đề tìm kiếm, cụ thể là truy xuất thông tin được lưu trữ trong một số cấu trúc dữ liệu hoặc được tính toán trong không gian tìm kiếm của miền vấn đề, với các giá trị rời rạc hoặc liên tục
Các thuật toán tìm kiếm được thiết kế để kiểm tra hoặc truy xuất một phần tử từ bất kỳ cấu trúc dữ liệu nào mà phần tử đó đang được lưu trữ. Họ tìm kiếm mục tiêu [khóa] trong không gian tìm kiếm
Các loại thuật toán tìm kiếm
Trong bài đăng này, chúng ta sẽ thảo luận về hai loại thuật toán tìm kiếm quan trọng
- Tìm kiếm tuyến tính hoặc tuần tự
- Tìm kiếm nhị phân
Hãy thảo luận chi tiết về hai vấn đề này với các ví dụ, triển khai mã và phân tích độ phức tạp về thời gian
Tìm kiếm tuyến tính hoặc tuần tự
Thuật toán này hoạt động bằng cách lặp lại tuần tự toàn bộ mảng hoặc danh sách từ một đầu cho đến khi tìm thấy phần tử đích. Nếu phần tử được tìm thấy, nó sẽ trả về chỉ mục của nó, ngược lại -1
Bây giờ hãy xem một ví dụ và cố gắng hiểu nó hoạt động như thế nào
arr = [2, 12, 15, 11, 7, 19, 45]
Giả sử phần tử mục tiêu mà chúng tôi muốn tìm kiếm là
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
3Phương pháp tìm kiếm tuyến tính hoặc tuần tự
- Bắt đầu với chỉ số 0 và so sánh từng phần tử với mục tiêu
- Nếu mục tiêu được tìm thấy bằng với phần tử, hãy trả về chỉ mục của nó
- Nếu không tìm thấy mục tiêu, trả về -1
Triển khai mã
Bây giờ hãy xem cách chúng tôi triển khai loại thuật toán tìm kiếm này trong một vài ngôn ngữ lập trình khác nhau
Tìm kiếm tuyến tính hoặc tuần tự trong Java
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
Tìm kiếm tuyến tính hoặc tuần tự trong Python
def search[nums, target]:
for i in range[len[nums]]:
if nums[i] == target:
return i
return -1
if __name__ == '__main__':
nums = [2, 12, 15, 11, 7, 19, 45]
target = 7
print[search[nums, target]]
Phân tích độ phức tạp thời gian
Trường hợp tốt nhất xảy ra khi phần tử đích là phần tử đầu tiên của mảng. Số lần so sánh, trong trường hợp này, là 1. Vì vậy, độ phức tạp thời gian là
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
4Trường hợp trung bình. Trung bình, phần tử đích sẽ ở đâu đó ở giữa mảng. Số lần so sánh, trong trường hợp này, sẽ là N/2. Vì vậy, độ phức tạp của thời gian sẽ là
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
5 [hằng số bị bỏ qua]Trường hợp xấu nhất xảy ra khi phần tử đích là phần tử cuối cùng trong mảng hoặc không có trong mảng. Trong trường hợp này, chúng ta phải duyệt qua toàn bộ mảng và do đó số phép so sánh sẽ là N. Vì vậy, độ phức tạp thời gian sẽ là
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
5Tìm kiếm nhị phân
Loại thuật toán tìm kiếm này được sử dụng để tìm vị trí của một giá trị cụ thể có trong một mảng được sắp xếp. Thuật toán tìm kiếm nhị phân hoạt động theo nguyên tắc chia để trị và nó được coi là thuật toán tìm kiếm tốt nhất vì chạy nhanh hơn
Bây giờ, hãy lấy một mảng đã sắp xếp làm ví dụ và cố gắng hiểu cách thức hoạt động của nó
arr = [2, 12, 15, 17, 27, 29, 45]
Giả sử phần tử mục tiêu được tìm kiếm là
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
7Phương pháp tìm kiếm nhị phân
- So sánh phần tử đích với phần tử ở giữa của mảng
- Nếu phần tử đích lớn hơn phần tử ở giữa thì tìm kiếm tiếp tục ở nửa bên phải
- Ngược lại, nếu phần tử đích nhỏ hơn giá trị ở giữa, quá trình tìm kiếm sẽ tiếp tục ở nửa bên trái
- Quá trình này được lặp lại cho đến khi phần tử ở giữa bằng phần tử đích hoặc phần tử đích không có trong mảng
- Nếu phần tử đích được tìm thấy, chỉ mục của nó được trả về, nếu không thì trả về -1
Triển khai mã
Tìm kiếm nhị phân trong Java
package algorithms.searching;
public class BinarySearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 17, 27, 29, 45};
int target = 17;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
int start = 0;
int end = nums.length - 1;
while [start target]
end = mid - 1;
else if [nums[mid] < target]
start = mid + 1;
else
return mid;
}
return -1;
}
}
Tìm kiếm nhị phân trong Python
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
0Phân tích độ phức tạp thời gian
Trường hợp tốt nhất xảy ra khi phần tử đích là phần tử ở giữa của mảng. Số lần so sánh, trong trường hợp này, là 1. Vì vậy, độ phức tạp thời gian là
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
4Trường hợp trung bình. Trung bình, phần tử đích sẽ ở đâu đó trong mảng. Vì vậy, độ phức tạp thời gian sẽ là
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
9Trường hợp xấu nhất xảy ra khi phần tử đích không có trong danh sách hoặc nó cách xa phần tử ở giữa. Vì vậy, độ phức tạp thời gian sẽ là
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
9Cách tính độ phức tạp của thời gian
Giả sử phép lặp trong Tìm kiếm nhị phân kết thúc sau k lần lặp
Tại mỗi lần lặp, mảng được chia cho một nửa. Vì vậy, giả sử độ dài của mảng tại bất kỳ lần lặp nào là N
Ở lần lặp 1,
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
4Ở lần lặp 2,
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
5Ở lần lặp 3,
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
6Tại lần lặp k,
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
7Ngoài ra, chúng ta biết rằng sau k lần chia, độ dài của mảng trở thành 1. Độ dài của mảng = N⁄2k = 1=> N = 2k
Nếu chúng ta áp dụng chức năng nhật ký trên cả hai mặt. log2 [N] = log2 [2k]=> log2 [N] = k log2 [2]
As [loga [a] = 1]
Do đó,=> k = log2 [N]
Vì vậy, bây giờ chúng ta có thể thấy tại sao độ phức tạp về thời gian của Tìm kiếm nhị phân là log2 [N]
Bạn cũng có thể hình dung hai thuật toán trên bằng công cụ đơn giản do Dipesh Patil xây dựng - Algorithms Visualizer
Tìm kiếm nhị phân theo thứ tự
Giả sử, chúng ta phải tìm một phần tử đích trong một mảng được sắp xếp. Chúng tôi biết rằng mảng được sắp xếp, nhưng chúng tôi không biết liệu nó được sắp xếp theo thứ tự tăng dần hay giảm dần
Phương pháp tìm kiếm nhị phân theo thứ tự
Cách thực hiện tương tự như tìm kiếm nhị phân ngoại trừ việc chúng ta cần xác định xem mảng được sắp xếp theo thứ tự tăng dần hay giảm dần. Điều này sau đó cho phép chúng tôi đưa ra quyết định về việc tiếp tục tìm kiếm ở nửa bên trái của mảng hay nửa bên phải của mảng
- Trước tiên chúng tôi so sánh mục tiêu với phần tử ở giữa
- Nếu mảng được sắp xếp theo thứ tự tăng dần và mục tiêu nhỏ hơn phần tử ở giữa HOẶC mảng được sắp xếp giảm dần và mục tiêu lớn hơn phần tử ở giữa, thì chúng ta tiếp tục tìm kiếm ở nửa dưới của mảng bằng cách đặt
1def search[nums, target]: for i in range[len[nums]]: if nums[i] == target: return i return -1 if __name__ == '__main__': nums = [2, 12, 15, 11, 7, 19, 45] target = 7 print[search[nums, target]]
- Mặt khác, chúng tôi thực hiện tìm kiếm ở nửa trên của mảng bằng cách đặt
2def search[nums, target]: for i in range[len[nums]]: if nums[i] == target: return i return -1 if __name__ == '__main__': nums = [2, 12, 15, 11, 7, 19, 45] target = 7 print[search[nums, target]]
Điều duy nhất chúng ta cần làm là tìm hiểu xem mảng được sắp xếp theo thứ tự tăng dần hay giảm dần. Chúng ta có thể dễ dàng tìm thấy điều này bằng cách so sánh các phần tử đầu tiên và cuối cùng của mảng
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
0Triển khai mã
Tìm kiếm nhị phân theo thứ tự trong Java
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
1Tìm kiếm nhị phân theo thứ tự trong Python
package algorithms.searching;
public class LinearSearch {
public static void main[String[] args] {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println[search[nums, target]];
}
static int search[int[] nums, int target] {
for [int index = 0; index < nums.length; index++] {
if [nums[index] == target] {
return index;
}
}
return -1;
}
}
2Phân tích độ phức tạp thời gian
Sẽ không có thay đổi về độ phức tạp của thời gian, vì vậy nó sẽ giống như Tìm kiếm nhị phân
Sự kết luậnTrong bài viết này, chúng ta đã thảo luận về hai trong số các thuật toán tìm kiếm quan trọng nhất cùng với cách triển khai mã của chúng trong Python và Java. Chúng tôi cũng đã xem xét phân tích độ phức tạp thời gian của họ
Cảm ơn vì đã đọc
Đăng ký nhận bản tin của tôiQUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
Nhà phát triển ứng dụng tại Thoughtworks Ấn Độ
Nếu bạn đọc đến đây, hãy tweet cho tác giả để cho họ thấy bạn quan tâm. Tweet một lời cảm ơn
Học cách viết mã miễn phí. Chương trình giảng dạy nguồn mở của freeCodeCamp đã giúp hơn 40.000 người có việc làm với tư cách là nhà phát triển. Bắt đầu