Chuỗi tìm kiếm nhị phân Python

Tuyên bố vấn đề - Chúng tôi sẽ nhận được một danh sách đã sắp xếp và chúng tôi cần tìm một phần tử với sự trợ giúp của tìm kiếm nhị phân

thuật toán

• So sánh x với phần tử ở giữa

• Nếu x khớp với phần tử ở giữa, chúng tôi trả về chỉ số giữa

• Khác Nếu x lớn hơn phần tử giữa thì x chỉ có thể nằm ở nửa mảng con bên phải sau phần tử giữa. Vì vậy, chúng tôi lặp lại cho một nửa bên phải

  Tìm kiếm nhị phân Python tìm vị trí của một mục trong một mảng được sắp xếp. Nó chia một nửa danh sách. Nếu một giá trị được chỉ định cao hơn số ở giữa, tìm kiếm sẽ tập trung vào bên phải của danh sách. Mặt khác, tìm kiếm sẽ tìm số ở bên trái của danh sách

  Làm thế nào để bạn tìm thấy vị trí của một mục trong danh sách? . Bằng cách sử dụng tìm kiếm nhị phân, bạn có thể dễ dàng tìm thấy vị trí của một phần tử bên trong một mảng đã sắp xếp

  Tìm trận đấu Bootcamp của bạn

  • Career Karma kết hợp bạn với các bootcamp công nghệ hàng đầu
  • Truy cập học bổng độc quyền và các khóa học chuẩn bị
  Chọn sở thích của bạn
  Tên
  
  Họ
  
  Email
  
  Điện thoại .
  
  
  

  By continuing you agree to our Terms of Service and Privacy Policy, and you consent to receive offers and opportunities from Career Karma by telephone, text message, and email.

  Máy tính rất giỏi trong việc tìm kiếm thông qua các danh sách để tìm một mục cụ thể. Các quy tắc mà máy tính sử dụng để tìm các mục trong danh sách được gọi là thuật toán tìm kiếm. Một trong những thuật toán Python phổ biến nhất là tìm kiếm nhị phân

  Trong hướng dẫn này, chúng ta sẽ thảo luận về tìm kiếm nhị phân là gì và chúng hoạt động như thế nào. Chúng ta sẽ xem qua một ví dụ về tìm kiếm nhị phân trong Python để bạn có thể tìm hiểu cách viết một tìm kiếm vào chương trình của mình. Bắt đầu nào

  Tìm kiếm nhị phân Python là gì?

  Tìm kiếm nhị phân Python là một thuật toán tìm vị trí của một phần tử trong một mảng có thứ tự. Tìm kiếm nhị phân liên tục chia danh sách thành hai nửa. Sau đó, tìm kiếm sẽ so sánh nếu một giá trị cao hơn hoặc thấp hơn giá trị ở giữa trong danh sách

  Có hai cách bạn có thể thực hiện tìm kiếm nhị phân. Cả hai cách tiếp cận đều đặt con trỏ được sử dụng để theo dõi vị trí cao nhất và thấp nhất tại một điểm cụ thể trong một mảng

  Cách tiếp cận đầu tiên bạn có thể sử dụng là phương pháp lặp. Trong cách tiếp cận này, một tập hợp các câu lệnh được lặp lại để xác định vị trí của một phần tử trong một mảng. Trong Python, chúng tôi sử dụng vòng lặp while cho mục đích này

  Cách tiếp cận khác là phương pháp đệ quy. Đây là nơi bạn viết một hàm tự gọi đi gọi lại cho đến khi tìm thấy một phần tử trong danh sách. Phương pháp đệ quy sử dụng phương pháp chia để trị mà chúng ta đã thảo luận trước đó và lặp lại quá trình tìm kiếm cho đến khi tìm thấy một phần tử

  Cây tìm kiếm nhị phân Python. Từng bước một

  Với tất cả những gì nói về phép chia, phép chinh phục và đệ quy, có thể dễ dàng mất dấu chính xác cách thức hoạt động của tìm kiếm nhị phân. Vì lý do đó, chúng ta sẽ đi thẳng vào một ví dụ về cách hoạt động của tìm kiếm nhị phân. Hãy xem xét danh sách sau đây

  79142234

  Chúng tôi sẽ tìm kiếm số “22” trong danh sách của chúng tôi

  Để bắt đầu, chúng ta sẽ đặt hai con trỏ trong danh sách của mình. Một con trỏ sẽ phản ánh giá trị cao nhất trong danh sách và điểm kia sẽ phản ánh giá trị thấp nhất

  Thấp
  
  
  Cao79142234

  Bước tiếp theo của chúng tôi là tìm phần tử ở giữa trong mảng, đó là 14. Nếu giá trị này bằng với giá trị mà chúng tôi đang tìm kiếm, thì giá trị này sẽ được trả về

  Trong trường hợp này, 14 không giống như 22. Vì vậy, chương trình của chúng ta cần thực hiện phép so sánh

  » THÊM.   Thay thế mục trong danh sách bằng Python. Hướng dẫn đầy đủ

  Chúng ta sẽ so sánh số mà chúng ta đang tìm kiếm với phần tử ở giữa của các phần tử ở phía bên phải của phần tử ở giữa hiện tại. Chúng tôi sẽ chỉ làm điều này nếu số mà chúng tôi đang tìm kiếm lớn hơn số ở giữa. Nếu không, chúng tôi sẽ so sánh phần tử với phần tử ở giữa ở phía bên trái của phần tử ở giữa hiện tại

  Số 22 lớn hơn 14. Chương trình của chúng tôi bắt đầu so sánh 22 với phần tử ở giữa ở bên phải của phần tử ở giữa hiện tại của chúng tôi [14]. Trong trường hợp này, con số đó là 22. Điều này bằng với số mà chúng tôi đang tìm kiếm

  
  
  ThấpTrung bìnhCao79142234

  Chúng tôi đã tìm thấy giá trị trung bình của mình. Chương trình của chúng tôi bây giờ sẽ trả về vị trí chỉ mục của số đó. Trong trường hợp này, vị trí chỉ mục của 22 là 3 [hãy nhớ rằng danh sách được lập chỉ mục bắt đầu từ 0. ]

  Cách thực hiện tìm kiếm nhị phân trong Python

  Hãy làm bẩn tay với một số mã Python. Chúng ta sẽ khám phá cách triển khai Python của tìm kiếm nhị phân bằng cách sử dụng cả hai phương pháp mà chúng ta đã thảo luận trước đó. phương pháp lặp và đệ quy

  Tìm kiếm nhị phân lặp lại trong Python

  Chúng ta sẽ bắt đầu với phương pháp lặp đi lặp lại. Đây là nơi chúng tôi sẽ lặp qua mọi mục trong danh sách của chúng tôi. Sau đó, chúng ta sẽ tìm giá trị ở giữa trong danh sách. Chúng tôi sẽ tiếp tục làm như vậy cho đến khi chúng tôi tìm thấy giá trị mà chúng tôi đang tìm kiếm

  Chức năng tìm kiếm nhị phân

  Hãy bắt đầu bằng cách xác định hàm Python cho tìm kiếm nhị phân của chúng tôi

  def findValue[numbers, number_to_find]:
  	low = 0
  	high = len[listnumbers - 1
  
  	while low = low:
  		middle = low + [high - low] // 2
  
  		if numbers[middle] == number_to_find:
  			return middle
  		elif numbers[middle] < number_to_find:
  			return findValue[numbers, number_to_find, middle + 1, high]
  		else:
  			return findValue[numbers, number_to_find, low, middle - 1]
  	
  	else:
  		return -1
  

  Mã của chúng tôi hơi giống với ví dụ cuối cùng của chúng tôi

  Chúng tôi bắt đầu bằng cách kiểm tra xem giá trị cao nhất có lớn hơn hoặc bằng thấp không. Nếu đúng, chương trình của chúng ta sẽ trả về -1. Nếu không, nó sẽ bắt đầu thực hiện tìm kiếm nhị phân

  Chúng tôi tính toán số ở giữa bằng cách sử dụng phương pháp tương tự như trong ví dụ trước. Đầu tiên, chúng tôi trừ giá trị thấp nhất từ ​​​​giá trị cao nhất. Sau đó, chúng tôi tính modulo [phần dư] của giá trị đó khi chia cho 2. Cuối cùng, chúng tôi thêm số thấp nhất

  Sau đó, chúng tôi đã viết một câu lệnh if quyết định cách tiến hành tìm kiếm nhị phân của chúng tôi

  • Nếu số ở giữa bằng với số chúng ta đang tìm kiếm, vị trí của số đó được trả về
  • Nếu số ở giữa nhỏ hơn số chúng ta đang tìm kiếm, hàm findValue[] của chúng ta sẽ được gọi lại. Lần này, giá trị thấp được đặt bằng một giá trị lớn hơn giá trị trung bình của chúng tôi
  • Nếu số ở giữa lớn hơn số chúng ta đang tìm kiếm, hàm findValue[] được gọi. Giá trị của “cao” sẽ bằng một ít hơn giá trị trung bình

  » THÊM.   Cách học lập trình bằng Python

  Viết chương trình chính

  Tất cả những gì chúng ta phải làm là viết chương trình chính của chúng ta

  numbers = [7, 9, 14, 22, 34]
  number_to_find = 22
  
  final = findValue[numbers, number_to_find, 0, len[numbers] - 1]
  
  if final == -1:
  	print["This item was not found in the list."]
  else:
  	print["The number " + str[number_to_find] + " was found at index position " + str[final] + "."]
  

  Chương trình chính của chúng tôi giống như ví dụ trước của chúng tôi về một điểm khác biệt. Chúng tôi đang chuyển hai tham số mới cho hàm findValue[] của chúng tôi. thấp và cao

  Chúng tôi cần làm điều này vì thuật toán của chúng tôi là đệ quy và chúng tôi không thể gán các giá trị đó trong hàm của mình. Nếu chúng tôi đã chỉ định các giá trị trong hàm của mình, các giá trị đó sẽ được đặt lại mỗi khi hàm của chúng tôi thực thi, điều này sẽ phá vỡ thuật toán tìm kiếm của chúng tôi

  mã của chúng tôi trả về

  The number 22 was found at index position 3.

  Chúng tôi đã nhận được kết quả tương tự từ trước đó. Trong ví dụ này, chúng tôi đã sử dụng chương trình đệ quy thay vì chương trình lặp để thực hiện tìm kiếm nhị phân của mình

  Khi nào bạn nên sử dụng tìm kiếm nhị phân Python?

  Tìm kiếm nhị phân là một cách hiệu quả để tìm kiếm thông qua danh sách các số. Tìm kiếm này hiệu quả hơn tìm kiếm tuyến tính. Điều này là do phương pháp nhị phân cắt giảm tìm kiếm của bạn xuống một nửa ngay khi bạn tìm thấy phần giữa của danh sách được sắp xếp

  Điều quan trọng cần lưu ý là một danh sách phải được sắp xếp theo thứ tự số trước khi có thể tìm kiếm nó bằng tìm kiếm nhị phân. Trước khi bạn thực hiện tìm kiếm nhị phân, hãy đảm bảo các số của bạn được sắp xếp theo thứ tự tăng dần

  Tìm kiếm nhị phân trong Phân tích độ phức tạp của Python

  Độ phức tạp của tìm kiếm nhị phân là gì?

  Thuật toán tìm kiếm nhị phân có độ phức tạp trường hợp tốt nhất là O[1]. Điều này xảy ra khi lần so sánh đầu tiên bằng với mục mà bạn đang tìm kiếm

  Độ phức tạp trung bình và trường hợp xấu nhất cho tìm kiếm nhị phân là O[log n]. Điều này có nghĩa là khoảng thời gian cần thiết để tiến hành tìm kiếm tăng theo logarit tùy thuộc vào số lượng mục cần tìm kiếm trong danh sách

  Sự kết luận

  Tìm kiếm nhị phân là một cách hiệu quả để tìm vị trí chỉ mục của một giá trị trong danh sách

  Mỗi lần chạy tìm kiếm nhị phân, tìm kiếm sẽ chia danh sách thành hai phần. Tìm kiếm tập trung vào phía của danh sách gần nhất với số mà bạn đang tìm kiếm

  Đối với mỗi lần chạy tìm kiếm, số lượng số mà chương trình cần tìm kiếm sẽ giảm đi một nửa

  Để tìm hiểu thêm về Python, hãy đọc hướng dẫn Cách học Python của chúng tôi

  1 Xếp hạng

  
  
  

  Về chúng tôi. Career Karma là một nền tảng được thiết kế để giúp người tìm việc tìm kiếm, nghiên cứu và kết nối với các chương trình đào tạo việc làm để thăng tiến trong sự nghiệp của họ. Tìm hiểu về ấn phẩm CK

  Tìm kiếm nhị phân có thể được sử dụng cho chuỗi Python không?

  Cho một mảng Chuỗi đã sắp xếp và Chuỗi x, hãy tìm chỉ mục của x nếu nó có trong mảng . Chuỗi x có mặt ở chỉ mục 2.

  Tìm kiếm nhị phân có thể được sử dụng cho các chuỗi không?

  Tìm kiếm nhị phân là kỹ thuật tìm kiếm hoạt động bằng cách tìm phần giữa của mảng để tìm phần tử. Đối với mảng các chuỗi, thuật toán tìm kiếm nhị phân cũng sẽ giữ nguyên . Nhưng các so sánh được thực hiện sẽ dựa trên so sánh chuỗi.

  Tìm kiếm nhị phân được thực hiện như thế nào trong Python?

  Tìm kiếm nhị phân so sánh giá trị đích với phần tử ở giữa của mảng. Nếu chúng không bằng nhau, nửa mà mục tiêu không thể nói dối sẽ bị loại bỏ và quá trình tìm kiếm tiếp tục trên nửa còn lại, một lần nữa lấy phần tử ở giữa để so sánh với giá trị mục tiêu và lặp lại điều này cho đến khi tìm thấy giá trị mục tiêu

  Tìm kiếm nhị phân với ví dụ trong Python là gì?

  Tìm kiếm nhị phân trong python là kỹ thuật tìm kiếm hoạt động trên một mảng được sắp xếp . Thay vì so sánh từng phần tử của mảng với phần tử được yêu cầu, thuật toán tìm kiếm nhị phân liên tục chia mảng thành các mảng con rồi tìm kiếm phần tử được yêu cầu trong mảng con.