Độ phức tạp của thuật toán tìm kiếm nhị phân năm 2024

Tìm kiếm nhị phân (Binary Search) là một thuật toán tìm kiếm nhanh với độ phức tạp trong thời gian chạy là Ο(log n). Thuật toán tìm kiếm này hoạt động theo nguyên tắc chia để trị. Để thuật toán này có thể hoạt động bình thường, việc thu thập dữ liệu phải ở dạng đã được sắp xếp.

Binary Search tìm kiếm một mục cụ thể bằng cách so sánh mục ở giữa nhất của bộ sưu tập. Nếu khớp xảy ra, thì chỉ mục của mục được trả về. Nếu mục ở giữa lớn hơn mục, thì mục đó được tìm kiếm trong mảng con bên trái của mục ở giữa. Mặt khác, mục được tìm kiếm sẽ nằm trong mảng phụ ở bên phải của mục ở giữa. Quá trình này cũng tiếp tục trên mảng con cho đến khi kích thước của mảng con giảm xuống bằng không.

Tìm kiếm nhị phân hoạt động như thế nào?

Để tìm kiếm nhị phân hoạt động, bắt buộc phải sắp xếp mảng mục tiêu. Chúng ta sẽ tìm hiểu quá trình tìm kiếm nhị phân với một ví dụ bằng hình ảnh. Sau đây là mảng đã sắp xếp của chúng ta và giả sử rằng chúng ta cần tìm kiếm vị trí của giá trị 31 bằng cách sử dụng tìm kiếm nhị phân.

Đầu tiên, chúng ta sẽ xác định một nửa mảng bằng cách sử dụng công thức này:

mid = low + (high - low) / 2

Đây là 0 + (9 – 0 ) / 2 = 4 (giá trị nguyên là 4,5). Vì vậy, 4 là giữa của mảng.

Bây giờ, chúng ta so sánh giá trị được lưu trữ tại vị trí 4, với giá trị đang được tìm kiếm, tức là 31. Chúng ta thấy rằng giá trị tại vị trí 4 là 27, giá trị này không khớp. Vì giá trị lớn hơn 27 và chúng ta có một mảng được sắp xếp, nên chúng ta cũng biết rằng giá trị đích phải nằm ở phần trên của mảng.

Chúng ta thay đổi mức thấp thành mức trung bình + 1 và tìm lại giá trị mức trung bình mới.

low = mid + 1 mid = low + (high - low) / 2

Trung bình mới của chúng ta bây giờ là 7. Ta so sánh giá trị được lưu trữ tại vị trí 7 với giá trị mục tiêu 31.

Giá trị được lưu trữ tại vị trí 7 không khớp, thay vào đó, nó lớn hơn mục tiêu tìm kiếm. Vì vậy, giá trị phải ở phần dưới từ vị trí này.

Do đó, ta tính toán lại giữa. Lần này là 5.

So sánh giá trị được lưu trữ tại vị trí 5 với giá trị mục tiêu. Ta thấy trùng khớp.

Chúng ta kết luận rằng giá trị mục tiêu 31 được lưu trữ tại vị trí 5.

Tìm kiếm nhị phân giảm một nửa các mục có thể tìm kiếm và do đó làm giảm số lần so sánh được thực hiện với số lượng rất ít.

Pseudocode

Pseudocode của thuật toán binary search trông sẽ như thế này:

`Procedure binary_search A ← sorted array n ← size of array x ← value to be searched Set lowerBound = 1 Set upperBound = n while x not found

  if upperBound < lowerBound 
     EXIT: x does not exists.
  set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
  if A[midPoint] < x
     set lowerBound = midPoint + 1
  if A[midPoint] > x
     set upperBound = midPoint - 1 
  if A[midPoint] = x 
     EXIT: x found at location midPoint

end while end procedure`Code language: PHP (php)

Nếu bạn muốn hiểu sâu hơn về Binary Search, đăng ký ngay lớp học thuật toán FSE Big Tech – học trực tiếp từ giảng viên hiện đang làm việc tại các công ty hàng đầu như Google, Amazon, TikTok, Booking, Grab!

Thuật toán tìm kiếm nhị phân (Binary Search) được sử dụng để tìm kiếm một giá trị trong một danh sách đã sắp xếp. Thuật toán này cài đặt theo phương pháp đệ quy sẽ giảm số phép toán so sánh và làm cho thuật toán chạy nhanh hơn. Trong trường hợp tệ nhất thì độ phức tạp của thuật toán sẽ là O(log n), với n là số phần tử của mảng.

Cách thực hiện

Ví dụ chúng ta có một mảng gồm các phần tử 1 2 4 6 7 8 9 10. Bây giờ chúng ta nhập vào một số nào đó. Ví dụ số cần tìm x=9, thuật toán sẽ làm như sau:

• Lấy giá trị chính giữa của dãy số y so sánh với x, nếu x nhỏ hơn thì tìm trong danh sách từ phần tử đầu tiên đến trước phần tử y, ngược lại thì tìm từ phần tử ngay sau y đến phần tử cuối cùng.
• Lặp lại bước trên cho đến khi gặp được x.

Đã tìm được x ở vị trí số 7.

Yêu cầu

Viết chương trình để cài đặt thuật toán tìm kiếm nhị phân (Binary Search) để tìm kiếm giá trị trong một mảng đã sắp xếp.

Phân tích và tìm cách giải

• Đầu vào: Một mảng số đã sắp xếp, giá trị x cần tìm.
• Đầu ra: In ra vị trí tìm được trong mảng
• Phân tích:
  • – Hàm sử tìm kiếm BinarySearch(a[], start, end)
  • – Tính k=(start + end)/2
  • – Bước cơ sở:
  • If a[k] = x -> return k //tìm thấy
  • If k=end -> return -1 //không tìm thấy
  • Bước đệ qui:
  • If a[k]
  • BinarySearch(a[], start, k-1)
  • Else
  • BinarySearch(a[], k+1, end)

Cách biểu diễn thuật toán tìm kiếm nhị phân (Binary Search)

Trong trường hợp này, tôi sử dụng ngôn ngữ giả.

Declare int a[] ={1, 2, 4, 6, 7, 8, 9, 10}

Input x

Binary(a[],x,start,end){

Int k = (start + end)/2

If a[k]=x then return k //Tìm thấy tại vị trí k

If k=end then return -1 // Không tìm thấy

If a[k]>x then

Binary(a[],x,start,k-1)

Else

Binary(a[],x,k+1,end)

`Input x `0

Trên đây là một số thuật toán cơ bản, hay gặp nhằm giúp các bạn mới học thuật toán dễ dàng tiếp cận. Trong thời gian tới tôi sẽ tiếp tục cập nhật những thuật toán ở cấp độ khó hơn để các bạn có cơ hội rèn luyện sâu hơn.

Thuật toán tìm kiếm nhị phân cần bao nhiêu bước?

Thuật toán tìm kiếm nhị phân cần 4 bước để tìm thấy Mai trong danh sách [“Hoa”, “Lan”, “Mai”, “Phong”, “Vy”].

Thuật toán tìm kiếm nhị phân áp dụng với dãy số như thế nào?

Tìm kiếm nhị phân - Binary search được sử dụng trên dãy số đã được sắp xếp tăng dần hoặc giảm dần. Khác với tìm kiếm tuyến tính không cần điều kiện gì về dãy số tìm kiếm thì với tìm kiếm nhị phân ta phải có một dãy số đã có thứ tự hoặc phải sắp xếp dãy số trước khi áp dụng thuật toán này.

Tìm kiếm nhị phân là gì?

Trong khoa học máy tính, tìm kiếm nhị phân (tiếng Anh: binary search), còn gọi là tìm kiếm nửa khoảng (half-interval search), tìm kiếm logarit (logarithmic search), hay chặt nhị phân (binary chop), là một thuật toán tìm kiếm xác định vị trí của một giá trị cần tìm trong một mảng đã được sắp xếp.

Cây tìm kiếm nhị phân là gì?

Định nghĩa Cây tìm kiếm nhị phân là một cấu trúc dữ liệu cơ bản được sử dụng để xây dựng các cấu trúc dữ liệu trừu tượng hơn như các tập hợp, đa tập hợp, các dãy kết hợp. Nếu một BST có chứa các giá trị giống nhau thì nó biểu diễn một đa tập hợp. Cây loại này sử dụng các bất đẳng thức không nghiêm ngặt.