Mô phỏng thuật toán Binary Search

Binary Search là thuật toán tìm kiếm hiệu quả trong mảng đã sắp xếp. Nó hoạt động bằng cách liên tục chia đôi phạm vi tìm kiếm cho đến khi tìm thấy phần tử hoặc xác định phần tử không tồn tại.

Left

Right

Mid

Phần tử tìm thấy

def binary_search(arr, x):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            return mid  # tìm thấy
        elif arr[mid] < x:
            left = mid + 1  # tìm bên phải
        else:
            right = mid - 1  # tìm bên trái
    return -1  # không tìm thấy
        

Nhật ký thực thi:

"; /* */

Binary Search Visualization

Mô phỏng thuật toán Binary Search

Left

Right

Mid

Phần tử tìm thấy

def binary_search(arr, x):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            return mid  # tìm thấy
        elif arr[mid] < x:
            left = mid + 1  # tìm bên phải
        else:
            right = mid - 1  # tìm bên trái
    return -1  # không tìm thấy
        