DAA - Tìm kiếm nhị phân

Trong chương này, chúng ta sẽ thảo luận về một thuật toán khác dựa trên phương pháp chia và chinh phục.

Báo cáo vấn đề

Tìm kiếm nhị phân có thể được thực hiện trên một mảng được sắp xếp. Trong cách tiếp cận này, chỉ mục của một phần tửxđược xác định nếu phần tử thuộc danh sách các phần tử. Nếu mảng không được sắp xếp, tìm kiếm tuyến tính được sử dụng để xác định vị trí.

Giải pháp

Trong thuật toán này, chúng tôi muốn tìm liệu phần tử x thuộc về một tập hợp các số được lưu trữ trong một mảng numbers[]. Ở đâul và r đại diện cho chỉ mục bên trái và bên phải của một mảng con mà thao tác tìm kiếm sẽ được thực hiện.

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then  
   return l  
else 
   m := ⌊(l + r) / 2⌋ 
   if x ≤ numbers[m]  then 
      return Binary-Search(numbers[], x, l, m) 
   else 
      return Binary-Search(numbers[], x, m+1, r)

Phân tích

Tìm kiếm tuyến tính chạy trong O(n)thời gian. Trong khi tìm kiếm nhị phân tạo ra kết quả trongO(log n) thời gian

Để cho T(n) là số so sánh trong trường hợp xấu nhất trong một mảng n các yếu tố.

Vì thế,

$$ T (n) = \ begin {case} 0 & if \: n = 1 \\ T (\ frac {n} {2}) + 1 & nếu không thì \ end {case} $$

Sử dụng quan hệ lặp lại này $ T (n) = log \: n $.

Do đó, tìm kiếm nhị phân sử dụng $ O (log \: n) $ time.

Thí dụ

Trong ví dụ này, chúng ta sẽ tìm kiếm phần tử 63.