Triển khai thuật toán tìm kiếm trong Python

Spread the love

Thực hiện tìm kiếm luôn là một thách thức nhưng không phải là không thể.

Trong cuộc sống thực, chúng ta sẽ không tìm kiếm theo khuôn mẫu nào. Chúng tôi chỉ đi đến những nơi mà chúng tôi nghĩ rằng nó có thể được đặt. Chúng tôi không tuân theo bất kỳ khuôn mẫu nào trong hầu hết các trường hợp.

Đ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 kiếm mọi thứ trong các chương trình. Chúng ta sẽ thấy một số thuật toán tuân theo các mẫu tìm kiếm khác nhau trong bài viết này.

Có nhiều thuật toán mà chúng ta có thể tìm thấy trong thế giới lập trình. 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 trong bài viết này. 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ả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ô hình 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ử. Nó dừng thực thi chương trình khi tìm thấy phần tử cần thiết.

Hãy minh họa các thuật toán tìm kiếm tuyến tính bằng một số hì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ô hình tìm kiếm, bạn sẽ thấy rằng thời gian dành cho việc thực hiện chương trình sẽ là O(n) trong trường hợp xấu nhất. Chúng ta phải xem xét độ phức tạp thời gian trong trường hợp xấu nhất của các thuật toán để phân tích. 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.

Triển khai 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. Đã đến lúc làm bẩn tay chúng ta với một số mã. Trước tiên hãy xem các bước để thực hiện tìm kiếm tuyến tính. Sau đó, bạn cố gắng mã hóa nó. Đừng lo lắng về ngay cả khi bạn không thể; Tôi sẽ cung cấp cho bạn mã sau đó.

  Làm cách nào để bạn quản lý tài khoản có thể nghe được của mình

Hãy xem các bước thực hiện 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 search_element, nhận ba đối số là mảng, độ dài của mảng và phần tử cần tìm.
  • search_element(mảng, n, phần tử):
    • Lặp lại mảng đã cho.
      • Kiểm tra xem phần tử hiện tại có bằng phần tử được yêu cầu hay không.
      • Nếu đúng thì trả về True.
    • Sau khi hoàn thành vòng lặp, nếu việc thực hiện vẫn còn trong hàm, thì phần tử không có trong mảng. Do đó trả về Sai.
  • In thông báo dựa trên giá trị trả về của hàm search_element.

Cuối cùng, viết mã với sự trợ giúp của các bước trên để triển khai thuật toán tìm kiếm tuyến tính.

Bạn đã hoàn thành việc triển khai thuật toán tìm kiếm tuyến tính chưa? Tôi cũng mong là như vậy. Nếu bạn đã hoàn thành, hãy kiểm tra chéo bằng mã sau.

Nếu bạn không hoàn thành nó, đừng lo lắng,; xem đoạn mã dưới đây và tìm hiểu cách chúng tôi triển khai nó. Bạn sẽ nhận đượ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 một phần tử có trong mảng. Và tiếp theo, 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 thêm một chút với các mẫu khác nhau không?

Vâng, chúng tôi có thể. Hãy xem nó.

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 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 trên mảng và kiểm tra phần tử ở giữa, nếu tìm thấy thì dừng chương trình. Ngược lại, nếu phần tử ở giữa nhỏ hơn phần tử bắt buộc, thì nó sẽ loại bỏ phần bên trái của mảng khỏi phần tử ở giữa khỏi quá trình tìm kiếm. Ngược lại, nếu phần tử ở giữa lớn hơn phần tử bắt buộc, thì nó sẽ bỏ qua phần bên phải của mảng từ phần tử ở giữa khi tìm kiếm.

  Làm thế nào để biết nếu ai đó đang từ chối cuộc gọi của bạn

Trong mỗi lần lặp, thuật toán tìm kiếm nhị phân cắt giảm khu vực để tìm kiếm phần tử. Vì vậy, 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.

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 chúng.

Độ 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ó đang giảm theo cấp số nhân.

Thực hiện tìm kiếm nhị phân

Đầu tiên, chúng ta sẽ xem các bước để thực hiện thuật toán tìm kiếm nhị phân và sau đó là mã. Hãy xem các bước để hoàn thành việc thực hiện 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 gọi là phần tử_tìm_kiếm, nhận ba đối số, mảng đã sắp xếp, độ dài của mảng và phần tử cần tìm.
  • search_element(sorted_arr, n, element):
    • Khởi tạo biến chỉ số i cho phép lặp mảng.
    • Tiếp theo, khởi tạo hai biến để duy trì vùng tìm kiếm của mảng. Ở đây, chúng tôi gọi chúng là bắt đầu và kết thúc khi chúng chỉ ra các chỉ mục.
    • 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. Đó sẽ là (bắt đầu + kết thúc) // 2.
      • Kiểm tra xem phần tử được lập chỉ mục ở giữa từ khu vực tìm kiếm có bằng phần tử được yêu cầu hay không.
      • Nếu đúng thì trả về True.
      • Ngược lại, nếu phần tử được lập chỉ mục ở giữa nhỏ hơn phần tử được yêu cầu, thì hãy di chuyển chỉ mục bắt đầu của khu vực tìm kiếm sang phần giữa + 1.
      • Ngược lại, nếu phần tử được lập chỉ mục ở giữa lớn hơn phần tử được yêu cầu, thì hãy di chuyển chỉ mục cuối của khu vực tìm kiếm sang giữa – 1.
      • Tăng chỉ số của mảng i.
    • Sau khi hoàn thành vòng lặp, nếu việc thực hiện vẫn còn trong hàm, thì phần tử không có trong mảng. Do đó trả về Sai.
  • In thông báo dựa trên giá trị trả về của hàm search_element.
  Phím tắt cho Lịch Google: Trang tính gian lận

Cố gắng viết mã tương tự như cách triển khai 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 thực hiện với đoạn mã dưới đây.

## 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ã 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.

Sự kết luận

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. Ta cần sắp xếp mảng cho thuật toán tìm kiếm nhị phân 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. Tuy nhiên, sử dụng các thuật toán hiệu quả để sắp xếp sẽ tạo thành một 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 đã có kiến ​​thức tốt về các thuật toán được sử dụng rộng rãi nhất trong Python.

Tiếp theo, hãy tìm hiểu một số phần mềm tìm kiếm tự lưu trữ phổ biến.

Mã hóa hạnh phúc 🙂 🧑‍💻

x