[Đệ quy] – Thuật toán tìm kiếm nhị phân (Binary Search) – iViettech

Posted on Updated on by adminChuyên mục:Kiến thức Internet
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 list đã sắp xếp. Thuật toán này setup theo chiêu thức đệ 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ố thành phần của mảng .

Cách thực hiện

Ví dụ tất cả chúng ta có một mảng gồm những thành phần 1 2 4 6 7 8 9 10. Bây giờ tất cả chúng ta nhập vào 1 số ít 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.

Thuat toan tim kiem nhi phan

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

Yêu cầu

Viết chương trình để setup 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 từ 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)

}

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

Bài trước: Thuật toán in dãy Fibonacci

admin