Giải thích Tìm kiếm nhị phân bằng Python

Tìm kiếm nhị phân là một thuật toán tìm kiếm được sử dụng để tìm kiếm một phần tử từ một mảng đã được sắp xếp. Nó không thể được sử dụng để tìm kiếm từ một mảng chưa được sắp xếp. Tìm kiếm nhị phân là một thuật toán hiệu quả và tốt hơn so với tìm kiếm tuyến tính về độ phức tạp thời gian.

Độ phức tạp thời gian của tìm kiếm tuyến tính là O (n). Trong khi độ phức tạp về thời gian của tìm kiếm nhị phân là O (log n). Do đó, tìm kiếm nhị phân là thuật toán tìm kiếm hiệu quả và nhanh hơn nhưng chỉ có thể được sử dụng để tìm kiếm từ một mảng được sắp xếp.

Tìm kiếm nhị phân hoạt động như thế nào?

Ý tưởng cơ bản đằng sau tìm kiếm nhị phân là thay vì so sánh phần tử bắt buộc với tất cả các phần tử của mảng, chúng ta sẽ so sánh phần tử bắt buộc với phần tử ở giữa của mảng. Nếu điều này hóa ra là yếu tố chúng ta đang tìm kiếm, thì chúng ta đã hoàn tất việc tìm kiếm thành công. Ngược lại, nếu phần tử chúng ta đang tìm nhỏ hơn phần tử ở giữa, thì chắc chắn phần tử đó nằm ở nửa đầu hoặc nửa trái của mảng, vì mảng đã được sắp xếp. Tương tự, nếu phần tử chúng ta đang tìm lớn hơn phần tử ở giữa, thì chắc chắn phần tử đó nằm ở nửa sau của mảng.

Do đó, tìm kiếm nhị phân liên tục giảm mảng thành một nửa. Quá trình trên được áp dụng đệ quy trên nửa mảng đã chọn cho đến khi chúng tôi tìm thấy phần tử mà chúng tôi đang tìm kiếm.

Chúng ta sẽ bắt đầu tìm kiếm với chỉ số bên trái 0 và chỉ số bên phải bằng với chỉ số cuối cùng của mảng. Chỉ số phần tử ở giữa (giữa) được tính là tổng của chỉ số bên trái và bên phải chia cho 2. Nếu phần tử bắt buộc nhỏ hơn phần tử ở giữa, thì chỉ số bên phải được thay đổi thành giữa 1, có nghĩa là bây giờ chúng ta sẽ chỉ nhìn vào nửa đầu của mảng. Tương tự như vậy, nếu phần tử được yêu cầu lớn hơn phần tử ở giữa, thì chỉ mục bên trái được thay đổi thành giữa + 1, có nghĩa là bây giờ chúng ta sẽ chỉ xem xét nửa sau của mảng. Chúng tôi sẽ lặp lại quy trình trên cho nửa mảng đã chọn.

Làm cách nào để biết nếu phần tử không có trong mảng?

Chúng ta cần có một số điều kiện để ngừng tìm kiếm thêm, điều này sẽ chỉ ra rằng phần tử không có trong mảng. Chúng tôi sẽ lặp đi lặp lại tìm kiếm phần tử trong mảng miễn là chỉ số bên trái nhỏ hơn hoặc bằng chỉ số bên phải. Khi điều kiện này chuyển thành false và chúng tôi vẫn chưa tìm thấy phần tử, điều này có nghĩa là phần tử không có trong mảng.

Ví dụ

Chúng ta hãy lấy mảng đã sắp xếp sau và chúng ta cần tìm kiếm phần tử 6.

L =0 H =8 Giữa =4

6 <10, do đó, hãy dành nửa đầu.

H =Giữa 1

L =0 H =3 Giữa =1

6> 5, do đó hãy chọn nửa sau.

L =Giữa + 1

L =2 H =3 Giữa =2

6 ==6, một phần tử được tìm thấy

Do đó, phần tử 6 được tìm thấy ở chỉ mục 2.

Thực hiện

Từ một mảng đã sắp xếp cho trước, hãy tìm kiếm một phần tử bắt buộc và in chỉ mục của nó nếu phần tử đó có trong mảng. Nếu phần tử không có, hãy in -1.

Mã để triển khai tìm kiếm nhị phân được đưa ra dưới đây.

Ví dụ

def binary_search(arr,x):
   l=0
   r=len(arr)-1
   while(l<=r):
      mid=(l+r)//2
      if(arr[mid]==x):
         return mid
      elif(x<arr[mid]):
         r=mid-1
      elif(x>arr[mid]):
         l=mid+1
   return -1
array=[1,2,3,4,5,6,7,8,9,10]
a=7
print(binary_search(array,a))
b=15
print(binary_search(array,b))

Đầu ra

6
-1

Yếu tố 7 hiện diện ở chỉ số 6.

Phần tử 15 không có trong mảng, do đó -1 được in.