Bài toán yêu cầu cài đặt hàm tìm kiếm nhị phân trên mảng đã được sắp xếp tăng dần, sử dụng con trỏ để truy cập dữ liệu. Nếu tìm thấy giá trị cần tìm, trả về chỉ số vị trí tương ứng; nếu không tìm thấy, trả về -1. Đồng thời, đếm và trả về số lần so sánh đã thực hiện trong quá trình tìm kiếm.

Định nghĩa giao diện hàm

int BinarySearch(int *arr, int length, int target, int *comparisons);
void BubbleSort(int *arr, int length);

Trong đó:

• arr: con trỏ trỏ đến phần tử đầu tiên của mảng.
• length: độ dài mảng.
• target: giá trị cần tìm.
• comparisons: con trỏ trỏ đến biến lưu số lần so sánh.

Hàm trả về: chỉ số của phần tử nếu tìm thấy, ngược lại trả về -1.

Ví dụ chương trình kiểm thử

#include <stdio.h>
#define MAX_SIZE 20

int BinarySearch(int *arr, int length, int target, int *comparisons);
void BubbleSort(int *arr, int length);

int main() {
    int data[MAX_SIZE], size, count;
    int result, value;
    int i, key;

    scanf("%d", &size);
    for (i = 0; i < size; i++) {
        scanf("%d", &data[i]);
    }
    scanf("%d", &key);

    BubbleSort(data, size);
    result = BinarySearch(data, size, key, &count);
    printf("%d\n%d\n", result, count);

    return 0;
}

Dữ liệu đầu vào mẫu 1

5
13 25 36 57 79
25

Kết quả đầu ra mẫu 1

1
3

Dữ liệu đầu vào mẫu 2

5
13 25 36 57 79
10

Kết quả đầu ra mẫu 2

-1
2

Cài đặt giải pháp

void BubbleSort(int *arr, int length) {
    for (int i = 0; i < length - 1; i++) {
        for (int j = 0; j < length - i - 1; j++) {
            if (*(arr + j) > *(arr + j + 1)) {
                int temp = *(arr + j);
                *(arr + j) = *(arr + j + 1);
                *(arr + j + 1) = temp;
            }
        }
    }
}

int BinarySearch(int *arr, int length, int target, int *comparisons) {
    int leftIndex = 0;
    int rightIndex = length - 1;
    int position = -1;
    *comparisons = 0;

    while (leftIndex <= rightIndex) {
        (*comparisons)++;
        int midIndex = leftIndex + (rightIndex - leftIndex) / 2;

        if (*(arr + midIndex) == target) {
            position = midIndex;
            break;
        }
        else if (*(arr + midIndex) < target) {
            leftIndex = midIndex + 1;
        }
        else {
            rightIndex = midIndex - 1;
        }
    }

    return position;
}