Việc thực hiện tìm kiếm luôn khó khăn, nhưng không phải là không thể.
Trong cuộc sống thực, chúng ta sẽ tìm kiếm không theo khuôn mẫu. Chúng tôi chỉ đi đến những nơi mà chúng tôi nghĩ rằng nó có thể được đặt. Hầu hết thời gian, chúng tôi không theo bất kỳ khuôn mẫu nào.
Điều tương tự có hoạt động trong thế giới lập trình không?
Không! phải có một số mẫu để tìm mọi thứ trong các chương trình. Trong bài viết này, chúng ta sẽ thấy một số thuật toán áp dụng các mẫu tìm kiếm khác nhau.
Có rất nhiều thuật toán mà chúng ta có thể tìm thấy trong thế giới lập trình. Trong bài viết này, chúng ta sẽ thảo luận về các thuật toán quan trọng nhất và được sử dụng nhiều nhất. Và phần còn lại của các thuật toán sẽ là một miếng bánh để bạn tìm hiểu.
Tìm kiếm đề cập đến việc tìm kiếm một phần tử trong một mảng trong bài viết này.
Hãy xem từng người một.
tìm kiếm tuyến tính
Tên gợi ý rằng thuật toán tìm kiếm tuyến tính tuân theo một mẫu tuyến tính để tìm kiếm các phần tử trong một mảng. Thuật toán bắt đầu tìm phần tử từ đầu mảng và di chuyển đến cuối cho đến khi tìm được phần tử. Dừng thực thi chương trình khi tìm thấy mục cần thiết.
Hãy minh họa thuật toán tìm kiếm tuyến tính bằng một số hình ảnh minh họa thú vị để hiểu rõ hơn về thuật toán.
Nếu bạn quan sát kỹ mẫu tìm kiếm, bạn sẽ nhận thấy rằng thời gian cần thiết để thực hiện chương trình sẽ là O(n) trong trường hợp xấu nhất. Chúng ta cần xem xét độ phức tạp về thời gian của các thuật toán được phân tích trong trường hợp xấu nhất. Do đó độ phức tạp thời gian của thuật toán là O(n).
Hãy xem việc triển khai thuật toán tìm kiếm tuyến tính.
Thực hiện tìm kiếm tuyến tính
Bây giờ bạn đã hiểu rõ về thuật toán tìm kiếm tuyến tính. Thời gian để làm bẩn tay của bạn với một số mã. Trước tiên hãy xem cách triển khai tìm kiếm tuyến tính. Sau đó, bạn cố gắng mã hóa nó. Đừng lo lắng ngay cả khi bạn không thể; Tôi sẽ cung cấp mã sau.
Hãy xem cách triển khai thuật toán tìm kiếm tuyến tính.
- Khởi tạo một mảng các phần tử (con số may mắn của bạn).
- Viết một hàm có tên lookup_item nhận ba đối số, một mảng, độ dài của mảng và mục cần tìm kiếm.
- lookup_item(mảng, n, mục):
- Lặp qua mảng đã cho.
- Kiểm tra xem mục hiện tại có bằng mục yêu cầu không.
- Nếu đúng thì trả về True.
- Kết thúc vòng lặp, nếu hàm vẫn thực thi nghĩa là phần tử không có trong mảng. Do đó trả về Sai.
- Lặp qua mảng đã cho.
- In thông báo dựa trên giá trị do hàm search_element trả về.
Cuối cùng, viết mã bằng các bước trên để triển khai thuật toán tìm kiếm tuyến tính.
Bạn đã thực hiện xong thuật toán tìm kiếm tuyến tính chưa? Tôi hi vọng. Nếu bạn đã hoàn tất, hãy kiểm tra chéo bằng mã sau.
Nếu bạn chưa hoàn thành nó, đừng lo lắng; xem mã bên dưới và tìm hiểu cách chúng tôi triển khai mã đó. Bạn sẽ đạt được nó mà không cần nỗ lực nhiều.
## searching function def search_element(arr, n, element): ## iterating through the array for i in range(n): ## checking the current element with required element if arr[i] == element: ## returning True on match return True ## element is not found hence the execution comes here return False if __name__ == '__main__': ## initializing the array, length, and element to be searched arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] n = 10 element_to_be_searched = 6 # element_to_be_searched = 11 if search_element(arr, n, element_to_be_searched): print(element_to_be_searched, "is found") else: print(element_to_be_searched, "is not found")
Đầu tiên thực hiện chương trình với phần tử có trong mảng. Và sau đó thực hiện nó với một phần tử không có trong mảng.
Độ phức tạp thời gian của thuật toán tìm kiếm tuyến tính là O(n).
Chúng ta có thể giảm nó hơn nữa bằng các công thức khác không?
Vâng, chúng tôi có thể. Hãy xem nào.
Tìm kiếm nhị phân
Thuật toán tìm kiếm nhị phân luôn kiểm tra phần tử ở giữa của mảng. Thuật toán này tìm kiếm một phần tử trong một mảng đã được sắp xếp.
Thuật toán tìm kiếm nhị phân lặp qua mảng và kiểm tra phần tử ở giữa nếu tìm thấy, sau đó dừng chương trình. Mặt khác, nếu phần tử ở giữa nhỏ hơn phần tử bắt buộc, nó sẽ bỏ qua phần bên trái của mảng từ phần tử ở giữa trong quá trình tìm kiếm. Mặt khác, nếu phần tử ở giữa lớn hơn phần tử bắt buộc, nó sẽ bỏ qua phần bên phải của mảng từ phần tử ở giữa trong quá trình tìm kiếm.
Trong mỗi lần lặp, thuật toán tìm kiếm nhị phân giảm vùng tìm kiếm phần tử. Do đó, số lần kiểm tra ít hơn số lần kiểm tra được thực hiện trong thuật toán tìm kiếm tuyến tính.
Hình ảnh minh họa giúp chúng ta hiểu rõ hơn về thuật toán tìm kiếm nhị phân. Hãy kiểm tra xem chúng ra.
Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân là O(log n). Trong mỗi lần lặp lại, độ dài của vùng tìm kiếm giảm đi một nửa. Nó giảm theo cấp số nhân.
triển khai tìm kiếm nhị phân
Đầu tiên chúng ta sẽ xem các bước để triển khai thuật toán tìm kiếm nhị phân và sau đó là mã. Hãy xem cách hoàn thành việc triển khai thuật toán tìm kiếm nhị phân.
- Khởi tạo mảng với các phần tử (con số may mắn của bạn)
- Viết một hàm có tên lookup_item nhận ba đối số, một mảng đã sắp xếp, độ dài của mảng và mục cần tìm kiếm.
- search_element(sorted_arr, n, element):
- Khởi tạo biến chỉ mục i cho phép lặp của mảng.
- Sau đó khởi tạo hai biến giữ vùng tra cứu của mảng. Ở đây chúng tôi gọi chúng là bắt đầu và kết thúc vì chúng trỏ đến các chỉ số.
- Lặp lại cho đến khi tôi nhỏ hơn độ dài của mảng.
- Tính toán chỉ số giữa của khu vực tìm kiếm bằng cách sử dụng giá trị bắt đầu và kết thúc. Đây sẽ là (bắt đầu + kết thúc) // 2.
- Kiểm tra xem mục được lập chỉ mục ở giữa từ khu vực tìm kiếm có bằng với mục được yêu cầu hay không.
- Nếu đúng thì trả về True.
- Mặt khác, nếu mục được lập chỉ mục ở giữa nhỏ hơn mục được yêu cầu, hãy di chuyển chỉ mục khu vực tìm kiếm ban đầu sang trung tâm+ 1.
- Mặt khác, nếu mục được lập chỉ mục ở giữa lớn hơn mục được yêu cầu, hãy di chuyển chỉ mục cuối của khu vực tìm kiếm vào giữa – 1.
- Tăng chỉ số mảng i.
- Kết thúc vòng lặp, nếu hàm vẫn thực thi nghĩa là phần tử không có trong mảng. Do đó trả về Sai.
- In thông báo dựa trên giá trị do hàm search_element trả về.
Hãy thử viết mã tương tự như thực hiện thuật toán tìm kiếm tuyến tính.
…
bạn đã nhận được mã?
Vâng, so sánh nó với mã dưới đây. Không, đừng lo lắng; hiểu việc triển khai với mã bên dưới.
## searching function def search_element(sorted_arr, n, element): ## array index for iteration i = 0 ## variables to track the search area ## initializing them with start and end indexes start = 0 end = n - 1 ## iterating over the array while i < n: ## getting the index of the middle element middle = (start + end) // 2 ## checking the middle element with required element if sorted_arr[middle] == element: ## returning True since the element is in the array return True elif sorted_arr[middle] < element: ## moving the start index of the search area to right start = middle + 1 else: ## moving the end index of the search area to left end = middle - 1 i += 1 return False if __name__ == '__main__': ## initializing the array, length, and element to be searched arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] n = 10 element_to_be_searched = 9 # element_to_be_searched = 11 if search_element(arr, n, element_to_be_searched): print(element_to_be_searched, "is found") else: print(element_to_be_searched, "is not found")
Kiểm tra mã của bạn với các trường hợp khác nhau trong đó phần tử có mặt và không có mặt trong một số trường hợp.
Đăng kí
Thuật toán tìm kiếm nhị phân hiệu quả hơn nhiều so với thuật toán tìm kiếm tuyến tính. Chúng ta cần sắp xếp mảng cho thuật toán tìm kiếm nhị phân, đây không phải là trường hợp của thuật toán tìm kiếm tuyến tính. Sắp xếp mất một thời gian. Nhưng sử dụng thuật toán sắp xếp hiệu quả sẽ là sự kết hợp tốt với thuật toán tìm kiếm nhị phân.
Bây giờ bạn đã hiểu rõ về các thuật toán được sử dụng phổ biến nhất trong Python.
Sau đó khám phá phần mềm tìm kiếm tự phục vụ phổ biến.
Chúc mừng mã hóa 🙂 🧑💻
