Thuật Toán đẹp: Tìm Nhị Phân | Python Cho Người Việt

Trang chủ » Thuật Toán Tìm Kiếm Python » Thuật Toán đẹp: Tìm Nhị Phân | Python Cho Người Việt

Có thể bạn quan tâm

Python Cho Người Việt Toggle navigation Python Cho Người Việt
  • Bài chỉ dẫn 2.5
  • Tin tức
  • Bài viết
  • Diễn đàn
  • Giới thiệu
Thuật toán đẹp: Tìm nhị phân

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

  • Mảng đã được sắp xếp nhưng đã bị xoay vòng (ví dụ [4, 5, 6, 7, 1, 2, 3]).
  • 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.

Fri 27 December 2013

By Nguyễn Thành Nam

Bài viết algorithm search binary

Từ khóa » Thuật Toán Tìm Kiếm Python