Tìm kiếm nhị phân DSA

Tìm kiếm nhị phân

Thuật toán Tìm kiếm nhị phân tìm kiếm trong một mảng và trả về chỉ mục của giá trị mà nó tìm kiếm.

Chạy mô phỏng để xem thuật toán Tìm kiếm nhị phân hoạt động như thế nào.

Để xem điều gì xảy ra khi không tìm thấy giá trị, hãy thử tìm giá trị 5.

Tìm kiếm nhị phân nhanh hơn nhiều so với Tìm kiếm tuyến tính nhưng yêu cầu một mảng được sắp xếp để hoạt động.

Thuật toán tìm kiếm nhị phân hoạt động bằng cách kiểm tra giá trị ở giữa mảng. Nếu giá trị mục tiêu thấp hơn thì giá trị tiếp theo cần kiểm tra sẽ nằm ở giữa nửa bên trái của mảng. Cách tìm kiếm này có nghĩa là vùng tìm kiếm luôn bằng một nửa vùng tìm kiếm trước đó và đây là lý do tại sao thuật toán Tìm kiếm nhị phân lại nhanh như vậy.

Quá trình giảm một nửa vùng tìm kiếm này diễn ra cho đến khi tìm thấy giá trị đích hoặc cho đến khi vùng tìm kiếm của mảng trống.

Chạy qua thủ công

Hãy thử thực hiện tìm kiếm theo cách thủ công, để hiểu rõ hơn về cách hoạt động của Tìm kiếm nhị phân trước khi thực sự triển khai nó bằng ngôn ngữ lập trình. Chúng tôi sẽ tìm kiếm giá trị 11.

Bước 1: Chúng ta bắt đầu với một mảng.

Bước 2: Giá trị ở giữa mảng tại chỉ số 3 có bằng 11 không?

Bước 3: 7 nhỏ hơn 11 nên ta phải tìm 11 ở bên phải chỉ số 3. Các giá trị ở bên phải chỉ số 3 là [ 11, 15, 25]. Giá trị tiếp theo cần kiểm tra là giá trị giữa 15, ở chỉ số 5.

Bước 4: 15 cao hơn 11 nên phải tìm ở bên trái chỉ số 5. ​​Chúng ta đã kiểm tra chỉ số 0-3 rồi nên chỉ số 4 chỉ còn giá trị cần kiểm tra.

Chúng tôi đã tìm thấy nó!

Giá trị 11 được tìm thấy ở chỉ số 4.

Trả về vị trí chỉ mục 4.

Tìm kiếm nhị phân đã hoàn tất.

Chạy mô phỏng bên dưới để xem các bước ở trên hoạt hình:

Chạy qua thủ công: Chuyện gì đã xảy ra?

Để bắt đầu, thuật toán có hai biến "trái" và "phải".

"left" là 0 và biểu thị chỉ mục của giá trị đầu tiên trong mảng và "right" là 6 và biểu thị chỉ mục của giá trị cuối cùng trong mảng.

\((left+right)/2=(0+6)/2=3\) là chỉ mục đầu tiên được sử dụng để kiểm tra xem giá trị ở giữa (7) có bằng giá trị đích (11) hay không.

7 thấp hơn giá trị đích 11, vì vậy trong vòng lặp tiếp theo, vùng tìm kiếm phải được giới hạn ở phía bên phải của giá trị ở giữa: [ 11, 15, 25], trên chỉ mục 4-6.

Để giới hạn vùng tìm kiếm và tìm giá trị ở giữa mới, "trái" được cập nhật thành chỉ mục 4, "phải" vẫn là 6. 4 và 6 là chỉ mục cho giá trị đầu tiên và cuối cùng trong vùng tìm kiếm mới, phía bên phải của giá trị trung bình trước đó. Chỉ số giá trị ở giữa mới là \((left+right)/2=(4+6)/2=10/2=5\).

Giá trị ở giữa mới trên chỉ mục 5 được kiểm tra: 15 cao hơn 11, vì vậy nếu giá trị đích 11 tồn tại trong mảng thì nó phải nằm ở phía bên trái của chỉ mục 5. Vùng tìm kiếm mới được tạo bằng cách cập nhật "right" từ 6 đến 4. Bây giờ cả "trái" và "phải" đều là 4, \((left+right)/2=(4+4)/2=4\), do đó chỉ còn lại chỉ số 4 để kiểm tra. Giá trị đích 11 được tìm thấy ở chỉ mục 4, do đó chỉ mục 4 được trả về.

Nói chung, đây là cách thuật toán Tìm kiếm nhị phân tiếp tục giảm một nửa diện tích tìm kiếm mảng cho đến khi tìm thấy giá trị đích.

Khi tìm thấy giá trị đích, chỉ mục của giá trị đích sẽ được trả về. Nếu không tìm thấy giá trị đích, -1 sẽ được trả về.

Triển khai tìm kiếm nhị phân

Để thực hiện thuật toán tìm kiếm nhị phân chúng ta cần:

1. Một mảng có các giá trị để tìm kiếm.
2. Một giá trị mục tiêu để tìm kiếm.
3. Một vòng lặp chạy miễn là chỉ mục bên trái nhỏ hơn hoặc bằng chỉ mục bên phải.
4. Câu lệnh if so sánh giá trị ở giữa với giá trị đích và trả về chỉ mục nếu tìm thấy giá trị đích.
5. Câu lệnh if kiểm tra xem giá trị đích có nhỏ hơn hay lớn hơn giá trị ở giữa hay không và cập nhật các biến "trái" hoặc "phải" để thu hẹp vùng tìm kiếm.
6. Sau vòng lặp, trả về -1, vì tại thời điểm này chúng ta biết giá trị đích vẫn chưa được tìm thấy.

Mã kết quả cho Tìm kiếm nhị phân trông như thế này:

 def binarySearch(arr, targetVal):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == targetVal:
            return mid
        
        if arr[mid] < targetVal:
            left = mid + 1
        else:
            right = mid - 1

    return -1

myArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
myTarget = 15

result = binarySearch(myArray, myTarget)

if result != -1:
    print("Value",myTarget,"found at index", result)
else:
    print("Target not found in array.")

Độ phức tạp thời gian tìm kiếm nhị phân

Để có giải thích chung về độ phức tạp của thời gian, hãy truy cập trang này .

Để được giải thích kỹ lưỡng và chi tiết hơn về độ phức tạp về thời gian Sắp xếp chèn, hãy truy cập trang này .

Mỗi lần Tìm kiếm nhị phân kiểm tra một giá trị mới để xem đó có phải là giá trị đích hay không, vùng tìm kiếm sẽ giảm đi một nửa.

Điều này có nghĩa là ngay cả trong trường hợp xấu nhất khi Tìm kiếm nhị phân không thể tìm thấy giá trị đích, nó vẫn chỉ cần so sánh \( \log_{2}n \) để xem qua một mảng các giá trị \(n\) đã được sắp xếp.

Độ phức tạp về thời gian của Tìm kiếm nhị phân là

\[ O( \log_{2} n ) \]

Nếu chúng ta rút ra lượng thời gian Tìm kiếm nhị phân cần để tìm một giá trị trong một mảng các giá trị \(n\), so với Tìm kiếm tuyến tính, chúng ta sẽ có biểu đồ này:

Chạy mô phỏng Tìm kiếm nhị phân bên dưới cho số lượng giá trị khác nhau \(n\) trong một mảng và xem cần bao nhiêu so sánh để Tìm kiếm nhị phân để tìm giá trị đích:

Như bạn có thể thấy khi chạy mô phỏng Tìm kiếm nhị phân, việc tìm kiếm yêu cầu rất ít so sánh, ngay cả khi mảng lớn và không tìm thấy giá trị mà chúng ta đang tìm kiếm.

Để thuật toán tìm kiếm nhị phân hoạt động,
mảng này phải có rồi .