Chương trình C tìm kiếm nhị phân (đệ quy và lặp)

Tìm kiếm nhị phân: thuật toán so sánh và chia đôi. Tìm vị trí giá trị mục tiêu trong mảng đã sắp xếp. So sánh với phần tử giữa. Nếu bằng thì trả về chỉ số. Nếu nhỏ hơn, tìm nửa đầu; lớn hơn, tìm nửa sau. Lặp lại cho đến khi tìm thấy.

Input: A[] = {0,2,6,11,12,18,34,45,55,99} n=55 Output: 55 at Index = 8

Giải thích

So sánh 55 với giữa mảng (18) -> 55 > 18 -> tìm nửa sau {34,45,55,99}. Giờ giữa là 55 -> khớp -> trả về chỉ số 8.

Hai cách cài đặt: lặp (dùng while) và đệ quy (gọi lại hàm với phạm vi mới).

Ví dụ (lặp)

#include<stdio.h>
int iterativeBsearch(int A[], int size, int element);

int main() {
    int A[] = {0,2,6,11,12,18,34,45,55,99};
    int n=55;
    printf("%d is found at Index %d \n",n,iterativeBsearch(A,10,n));
    return 0;
}

int iterativeBsearch(int A[], int size, int element) {
    int start = 0;
    int end = size-1;
    while(start<=end) {
        int mid = (start+end)/2;
        if( A[mid] == element) {
            return mid;
        } else if( element < A[mid] ) {
            end = mid-1;
        } else {
            start = mid+1;
        }
    }
    return -1;
}

Kết quả

55 is found at Index 8

Ví dụ (đệ quy)

#include<stdio.h>
int RecursiveBsearch(int A[], int start, int end, int element) {
    if(start>end) return -1;
    int mid = (start+end)/2;
    if( A[mid] == element ) return mid;
    else if( element < A[mid] )
        RecursiveBsearch(A, start, mid-1, element);
    else
        RecursiveBsearch(A, mid+1, end, element);
}

int main() {
    int A[] = {0,2,6,11,12,18,34,45,55,99};
    int n=55;
    printf("%d is found at Index %d \n",n,RecursiveBsearch(A,0,9,n));
    return 0;
}

Kết quả

55 is found at Index 8