Tìm kiếm nhị phân là một thuật toán tìm kiếm hiệu quả hoạt động trên các mảng được sắp xếp. Nó thường được sử dụng như một trong những ví dụ đầu tiên về thuật toán chạy trong thời gian logarit [O[logn]] vì hành vi trực quan của nó và là một thuật toán cơ bản trong Khoa học Máy tính
Tìm kiếm nhị phân - Ví dụ
Tìm kiếm nhị phân hoạt động theo cách tiếp cận chia để trị và dựa trên thực tế là mảng được sắp xếp để loại bỏ một nửa số ứng cử viên có thể có trong mỗi lần lặp. Cụ thể hơn, nó so sánh phần tử ở giữa của mảng đã sắp xếp với phần tử mà nó đang tìm kiếm để quyết định nơi tiếp tục tìm kiếm.
Nếu phần tử đích lớn hơn phần tử ở giữa - nó không thể nằm trong nửa đầu của bộ sưu tập nên nó bị loại bỏ. Điều tương tự cũng xảy ra theo cách khác
Ghi chú. Nếu mảng có số phần tử chẵn thì chúng ta sử dụng phần tử nào trong hai phần tử "ở giữa" để bắt đầu
Hãy xem nhanh một ví dụ trước khi chúng tôi tiếp tục giải thích cách hoạt động của tìm kiếm nhị phân
Như chúng ta có thể thấy, chúng ta biết chắc chắn rằng, vì mảng đã được sắp xếp nên x không nằm trong nửa đầu của mảng ban đầu
Khi chúng ta biết một nửa của mảng ban đầu x nằm ở đâu, chúng ta có thể lặp lại quá trình chính xác này với nửa đó và chia nó thành hai nửa một lần nữa, loại bỏ một nửa chắc chắn không chứa x
Chúng tôi lặp lại quá trình này cho đến khi chúng tôi kết thúc với một mảng con chỉ chứa một phần tử. Chúng tôi kiểm tra xem phần tử đó có phải là x không. Nếu đúng - chúng tôi đã tìm thấy x, nếu không - x hoàn toàn không tồn tại trong mảng
Nếu bạn xem xét kỹ hơn điều này, bạn có thể nhận thấy rằng trong trường hợp xấu nhất [x không tồn tại trong mảng], chúng ta cần kiểm tra số lượng phần tử nhỏ hơn nhiều so với số lượng chúng ta cần trong một mảng chưa sắp xếp - mà
Nói chính xác hơn, số phần tử chúng ta cần kiểm tra trong trường hợp xấu nhất là log2N trong đó N là số phần tử của mảng
Điều này tạo ra tác động lớn hơn khi mảng càng lớn
Nếu mảng của chúng ta có 10 phần tử, chúng ta chỉ cần kiểm tra 3 phần tử để tìm x hoặc kết luận nó không có ở đó. Đó là 33. 3%
Tuy nhiên, nếu mảng của chúng ta có 10.000.000 phần tử thì chúng ta chỉ cần kiểm tra 24 phần tử. đó là 0. 0002%
Thực hiện tìm kiếm nhị phân
Tìm kiếm nhị phân là một thuật toán đệ quy tự nhiên, vì quá trình tương tự được lặp lại trên các mảng nhỏ hơn và nhỏ hơn cho đến khi tìm thấy một mảng có kích thước 1. Tuy nhiên, tất nhiên cũng có cách triển khai lặp lại và chúng tôi sẽ chỉ ra cả hai cách tiếp cận
đệ quy
Hãy bắt đầu với việc triển khai đệ quy vì nó tự nhiên hơn
def binary_search_recursive[array, element, start, end]:
if start > end:
return -1
mid = [start + end] // 2
if element == array[mid]:
return mid
if element < array[mid]:
return binary_search_recursive[array, element, start, mid-1]
else:
return binary_search_recursive[array, element, mid+1, end]
Chúng ta hãy xem xét kỹ hơn mã này. Chúng tôi thoát khỏi đệ quy nếu phần tử
if start > end:
return -1
if start > end:
return -1
if start > end:
return -1
Điều này là do tình huống này chỉ xảy ra khi phần tử không tồn tại trong mảng. Điều xảy ra là cuối cùng chúng ta chỉ có một phần tử trong mảng con hiện tại và phần tử đó không khớp với phần tử chúng ta đang tìm kiếm
Tại thời điểm này,
if start > end:
return -1
if start > end:
return -1
if start > end:
return -1
if start > end:
return -1
if start > end:
return -1
if start > end:
return -1
Chúng tôi có thể đã làm điều này bằng cách sử dụng một cách tiếp cận khác
Hãy xem hướng dẫn thực hành, thực tế của chúng tôi để học Git, với các phương pháp hay nhất, tiêu chuẩn được ngành chấp nhận và bao gồm bảng gian lận. Dừng các lệnh Git trên Google và thực sự tìm hiểu nó
if len[array] == 1:
if element == array[mid]:
return mid
else:
return -1
Phần còn lại của mã thực hiện logic "kiểm tra phần tử ở giữa, tiếp tục tìm kiếm trong nửa thích hợp của mảng". Chúng tôi tìm chỉ mục của phần tử ở giữa và kiểm tra xem phần tử chúng tôi đang tìm kiếm có khớp với nó không
mid = [start + end] // 2
if elem == array[mid]:
return mid
Nếu không, chúng tôi kiểm tra xem phần tử nhỏ hơn hay lớn hơn phần tử ở giữa
Hãy tiếp tục và chạy thuật toán này, với một sửa đổi nhỏ để nó in ra mảng con mà nó hiện đang hoạt động
element = 18
array = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
print["Searching for {}".format[element]]
print["Index of {}: {}".format[element, binary_search_recursive[array, element, 0, len[array]]]]
Chạy mã này sẽ dẫn đến
Searching for 18
Subarray in step 0:[1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
Subarray in step 1:[16, 18, 24, 28, 29]
Subarray in step 2:[16, 18]
Subarray in step 3:[18]
Index of 18: 7
Có thể thấy rõ cách nó giảm một nửa không gian tìm kiếm trong mỗi lần lặp lại, ngày càng tiến gần hơn đến phần tử mà chúng ta đang tìm kiếm. Nếu chúng ta thử tìm kiếm một phần tử không tồn tại trong mảng, kết quả sẽ là
Searching for 20
Subarray in step 0: [4, 14, 16, 17, 19, 21, 24, 28, 30, 35, 36, 38, 39, 40, 41, 43]
Subarray in step 1: [4, 14, 16, 17, 19, 21, 24, 28]
Subarray in step 2: [19, 21, 24, 28]
Subarray in step 3: [19]
Index of 20: -1
Và để giải trí, chúng ta có thể thử tìm kiếm một số mảng lớn và xem có bao nhiêu bước để tìm ra một số tồn tại trong Tìm kiếm nhị phân
Searching for 421, in an array with 200 elements
Search finished in 6 steps. Index of 421: 169
Searching for 1800, in an array with 1500 elements
Search finished in 11 steps. Index of 1800: -1
Searching for 3101, in an array with 3000 elements
Search finished in 8 steps. Index of 3101: 1551
lặp đi lặp lại
Cách tiếp cận lặp lại rất đơn giản và tương tự như cách tiếp cận đệ quy. Ở đây, chúng tôi chỉ thực hiện kiểm tra trong vòng lặp
if start > end:
return -1
def binary_search_iterative[array, element]:
mid = 0
start = 0
end = len[array]
step = 0
while [start end:
return -1
Phần kết luận
Tìm kiếm nhị phân là một thuật toán đáng kinh ngạc để sử dụng trên các mảng lớn, được sắp xếp hoặc bất cứ khi nào chúng tôi định tìm kiếm các phần tử lặp đi lặp lại trong một mảng
Chi phí sắp xếp mảng một lần và sau đó sử dụng Tìm kiếm nhị phân để tìm các phần tử trong đó nhiều lần tốt hơn nhiều so với sử dụng Tìm kiếm tuyến tính trên một mảng chưa sắp xếp để chúng ta có thể tránh được chi phí sắp xếp mảng đó
Nếu chúng ta đang sắp xếp mảng và tìm kiếm một phần tử chỉ một lần, thì sẽ hiệu quả hơn nếu chỉ thực hiện Tìm kiếm tuyến tính trên mảng chưa sắp xếp