thuật toán tìm kiếm nhị phân

By Admin 21/04/2024 0

binary tìm kiếm main

1. Tìm Kiếm Nhị Phân

Bạn đang xem: thuật toán tìm kiếm nhị phân

Tìm lần nhị phân - Binary tìm kiếm được dùng bên trên sản phẩm số đang được bố trí tăng dần dần hoặc rời dần dần.

Khác với lần kiếm tuyến tính ko cần thiết ĐK gì về sản phẩm số lần kiếm thì với lần kiếm nhị phân tao nên với 1 sản phẩm số vẫn với trật tự hoặc là phải bố trí sản phẩm số trước lúc vận dụng thuật toán này.

Giả sử bạn phải lần kiếm thành phần X vô mảng A[] với N thành phần vẫn bố trí tăng dần dần. Ban đầu đoạn lần kiếm được xem là toàn cỗ mảng, chỉ số trước tiên của đoạn lần kiếm là 0 và chỉ số sau cuối là N - 1.

Ý tưởng của thuật toán này là ở từng chuyến lần kiếm bên trên đoạn [L, R] thì các bạn sẽ lần rời khỏi thành phần đứng thân thích và đối chiếu với thành phần X, vì như thế mảng vẫn bố trí tăng dần dần nên những lúc đối chiếu X với thành phần đứng thân thích bạn cũng có thể vô hiệu lên đường 1 nửa khoảng tầm lần lần, cứ như thế thì đoạn bạn phải lần kiếm tiếp tục giảm sút 1 nửa sau từng chuyến lần lần. 

Ví dụ mảng có một tỷ thành phần thì chúng ta chỉ việc lần kiếm 31 chuyến.

Để lần chỉ số đứng thân thích của đoạn [L, R] chúng ta lấy (L + R) / 2 hoặc L + (R - L) / 2

Thuật toán : 

  1. Chia song đoạn lần kiếm trở nên 2 nửa bằng phương pháp lần chỉ số đứng thân thích của đoạn cần thiết lần lần, M = (L + R) / 2
  2. So sánh thành phần ở thân thích đoạn là A[M] với thành phần cần thiết lần kiếm tiếp tục xẩy ra 3 ngôi trường hợp 
  3. Nếu thành phần cần thiết lần kiếm vày thành phần ở thân thích thì tóm lại lần thấy
  4. Nếu thành phần cần thiết lần kiếm nhỏ rộng lớn thành phần ở thân thích thì vô hiệu nửa ở bên phải vô chuyến lần kiếm tiếp theo
  5. Nếu thành phần cần thiết lần kiếm to hơn thành phần ở thân thích thì vô hiệu nửa phía trái vô chuyến lần kiếm tiếp theo
  6. Quá trình lặp lên đường tái diễn kể từ bước 1 cho tới bước 5 cho đến Khi thành phần được nhìn thấy hoặc không thể khoảng tầm lần kiếm

Trường phù hợp 1 : Khi lần rời khỏi thành phần đứng thân thích vày độ quý hiếm nhưng mà chúng ta lần lần, thuật toán tiếp tục ngừng vì như thế vẫn lần thấy

binary tìm kiếm 1

Trường phù hợp 2 : Khi lần rời khỏi thành phần đứng thân thích nhỏ rộng lớn độ quý hiếm lần lần, tao hoàn toàn có thể khẳng đỉnh độ quý hiếm cần thiết lần kiếm nếu như với tiếp tục nằm tại vị trí nửa ở bên phải. Khi cơ chúng ta cập nhập L = M + 1

binary tìm kiếm 2

Trường phù hợp 3 : Khi lần rời khỏi thành phần đứng thân thích to hơn độ quý hiếm lần lần, tao hoàn toàn có thể khẳng đỉnh độ quý hiếm cần thiết lần kiếm nếu như với tiếp tục nằm tại vị trí nửa phía trái. Khi cơ chúng ta cập nhập R = M - 1

binary tìm kiếm 3

Code : 

#include "stdio.h"

int binary_search(int a[], int n, int x){
    
    int l = 0, r = n - 1;
    while(l <= r){
        
        int m = (l + r) / 2;
        if(a[m] == x){
            return 1; 
        }
        else if(a[m] < x){
            
            l = m + 1;
        }
        else{
            
            r = m - 1;
        }
    }
    return 0; 
}

int main(){
    int n = 12, x = 24, hắn = 6;
    int a[12] = {1, 2, 3, 4, 5, 5, 7, 9, 13, 24, 27, 28};
    if(binary_search(a, n, x)){
        printf("FOUND\n");
    }
    else printf("NOT FOUND\n");
    if(binary_search(a, n, y)){
        printf("FOUND\n");
    }
    else printf("NOT FOUND\n");
    return 0;
}

Output : 

Xem thêm: sao kế đô tốt hay xấu

FOUND
NOT FOUND

Ví dụ 1. Tìm thành phần X = 3 vô mảng A[] = {1, 1, 3, 4, 5, 8, 9, 12, 21, 32}

Ban đầu : l = 0, r = 9

  1. Vòng lặp 1, l = 0, r = 9 , m = (l + r) / 2 = 4, A[m] = 5 > X => Cập nhật r = m - 1 = 3
  2. Vòng lặp 2, l = 0, r = 3, m = (l + r) / 2 = 1, A[m] = 1 < X => Cập nhật l = m + 1 = 2
  3. Vòng lặp 3, l = 2, r = 3, m = (l + r) / 2 = 2, A[m] = 3 = X => Tìm thấy X và kết đôn đốc chương trình 

Ví dụ 2. Tìm thành phần X = 2 vô mảng A[] = {1, 1, 3, 4, 5, 8, 9, 12, 21, 32}

Ban đầu : l = 0, r = 9

  1. Vòng lặp 1, l = 0, r = 9, m = (l + r) / 2 = 4, A[m] = 4 > X => Cập nhật r = m - 1 = 3
  2. Vòng lặp 2, l = 0, r = 3, m = (l + r) / 2 = 1, A[m] = 1 < X => Cập nhật l = m + 1 = 2
  3. Vòng lặp 3, l = 2, r = 3, m = (l + r) / 2 = 2, A[m] = 3 > X => Cập nhật r = m - 1 - 1
  4. Vòng lặp 4, l = 2, r = 1, l > r nên vòng lặp kết đôn đốc và không kiếm thấy X 

2. Tìm Kiếm Nhị Phân Biến Đổi

Bài toán 1. Tìm địa điểm trước tiên của thành phần X vô mảng vẫn chuẩn bị tăng dần

Tương tự động như thuật toán tìm kiếm nhị phân tuy nhiên Khi nhìn thấy thành phần X vô mảng thì tao chỉ đánh dấu thành quả và nỗ lực lần kiếm thêm thắt ở nửa phía trái.

#include "stdio.h"

int firstPos(int a[], int n, int x){
    int l = 0, r = n - 1;
    int pos = -1; 
    while(l <= r){
        
        int m = (l + r) / 2;
        if(a[m] == x){
            pos = m; 
            
            r = m - 1;
        }
        else if(a[m] < x){
            
            l = m + 1;
        }
        else{
            
            r = m - 1;
        }
    }
    return pos;
}

int main(){
    int n = 10, x = 3;
    int a[10] = {1, 1, 2, 2, 3, 3, 3, 5, 7, 9};
    int res = firstPos(a, n, x);
    if(res == -1){
        printf("%d khong xuat hien vô mang\n");
    }
    else{
        printf("Vi tri dau tien cua %d vô đem : %d\n", x, res);
    }
    return 0;
}

Output : 

Vi tri dau tien cua 3 vô đem : 4

Bài toán 2 : Tìm địa điểm sau cuối của thành phần X vô mảng vẫn chuẩn bị tăng dần

Tương tự động như thuật toán tìm kiếm nhị phân tuy nhiên Khi nhìn thấy thành phần X vô mảng thì tao chỉ đánh dấu thành quả và nỗ lực lần kiếm thêm thắt ở nửa ở bên phải.

#include "stdio.h"

int lastPos(int a[], int n, int x){
    int l = 0, r = n - 1;
    int pos = -1; 
    while(l <= r){
        
        int m = (l + r) / 2;
        if(a[m] == x){
            pos = m; 
            
            l = m + 1;
        }
        else if(a[m] < x){
            
            l = m + 1;
        }
        else{
            
            r = m - 1;
        }
    }
    return pos;
}

int main(){
    int n = 10, x = 3;
    int a[10] = {1, 1, 2, 2, 3, 3, 3, 5, 7, 9};
    int res = lastPos(a, n, x);
    if(res == -1){
        printf("%d khong xuat hien vô mang\n");
    }
    else{
        printf("Vi tri cuoi cung cua %d vô đem : %d\n", x, res);
    }
    return 0;
}

Output : 

Vi tri cuoi cung cua 3 vô đem : 6

Bài toán 3 : Tìm địa điểm trước tiên của thành phần to hơn hoặc vày X vô mảng vẫn chuẩn bị tăng dần

Tương tự động như thuật toán tìm kiếm nhị phân tuy nhiên Khi nhìn thấy thành phần ở thân thích to hơn hoặc vày thành phần X thì tao chỉ đánh dấu thành quả và nỗ lực lần kiếm thêm thắt ở nửa phía trái.

Xem thêm: phân tích sông đà trữ tình

#include "stdio.h"

int firstPos(int a[], int n, int x){
    int l = 0, r = n - 1;
    int pos = -1; 
    while(l <= r){
        
        int m = (l + r) / 2;
        if(a[m] >= x){
            pos = m; 
            
            r = m - 1;
        }
        else{
            
            l = m + 1;
        }
    }
    return pos;
}

int main(){
    int n = 10, x = 4;
    int a[10] = {1, 1, 2, 2, 3, 3, 3, 5, 7, 9};
    int res = firstPos(a, n, x);
    if(res == -1){
        printf("%d khong xuat hien vô mang\n");
    }
    else{
        printf("Vi tri dau tien cua phan tu >= %d vô đem : %d\n", x, res);
    }
    return 0;
}

Output : 

Vi tri dau tien cua phan tu >= 4 vô đem : 7

Xem thêm thắt bài bác giảng về Tìm Kiếm Nhị Phân của tôi : 

dB2DWSKGLj8