Python cho người Việt

Python cho người Việt

Entries tagged “binary”

Thuật toán đẹp: Tìm nhị phân

written by Nguyễn Thành Nam, on Dec 27, 2013 1:13:00 PM.

Mục đích

Tìm phần tử X trong một mảng đã được sắp xếp.

Ý tưởng chính

Chia mảng ra thành 3 cụm: cụm bên trái, phần tử ở giữa, và cụm bên phải. So sánh X với phần tử ở giữa. Nếu X bằng với phần tử ở giữa thì ta đã tìm được X trong mảng. Nếu X lớn hơn thì tìm X trong cụm bên phải. Nếu X nhỏ hơn thì tìm X trong cụm bên trái.

Hiệu quả

Thời gian thực hiện: O(logn)

Bộ nhớ cần thiết: O(1)

Cài đặt

Cài đặt đệ quy

def bin_search(x, a, left_idx, right_idx):
    if left_idx > right_idx:
        return -1
    mid_idx = left_idx + (right_idx - left_idx) // 2
    mid = a[mid_idx]
    if x == mid:
        return mid_idx
    elif x < mid:
        return bin_search(x, a, left_idx, mid_idx - 1)
    else:
        return bin_search(x, a, mid_idx + 1, right_idx)

assert bin_search(0, [0], 0, 0) == 0
assert bin_search(0, [1], 0, 0) == -1
assert bin_search(0, [0, 1], 0, 1) == 0
assert bin_search(1, [0, 1], 0, 1) == 1
assert bin_search(2, [0, 1], 0, 1) == -1

Cài đặt vòng lặp

def bin_search(x, a, left_idx, right_idx):
    while left_idx <= right_idx:
        mid_idx = left_idx + (right_idx - left_idx) // 2
        mid = a[mid_idx]
        if mid == x:
            return mid_idx
        elif x < mid:
            right_idx = mid_idx - 1
        else:
            left_idx = mid_idx + 1
    return -1

Tham khảo thêm

Mô-đun bisect trong thư viện chuẩn của Python.

Một số bài toán mở rộng

  1. Mảng đã được sắp xếp nhưng đã bị xoay vòng (ví dụ [4, 5, 6, 7, 1, 2, 3]).
  2. Mảng 2 chiều đã được sắp xếp theo dòng, và cột (a[i][j] < a[i + 1][j] và a[i][j] < a[i][j + 1]).

Các bạn có thể trao đổi ý tưởng giải quyết các bài toán mở rộng này trong diễn đàn.