C语言编程题实现二分查找

1、递归实现二分查找

#include <stdio.h>

// 递归实现二分查找
int binarySearchRecursive(int arr[], int left, int right, int target) {
    if (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
            return mid;

        if (arr[mid] > target)
            return binarySearchRecursive(arr, left, mid - 1, target);

        return binarySearchRecursive(arr, mid + 1, right, target);
    }

    return -1;  // 未找到
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    int result = binarySearchRecursive(arr, 0, n - 1, target);
    if (result == -1)
        printf("Element is not present in array\n");
    else
        printf("Element is present at index %d\n", result);
    return 0;
}

2、非递归实现二分查找

#include <stdio.h>

// 非递归实现二分查找
int binarySearchIterative(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
            return mid;

        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;  // 未找到
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    int result = binarySearchIterative(arr, n, target);
    if (result == -1)
        printf("Element is not present in array\n");
    else
        printf("Element is present at index %d\n", result);
    return 0;
}

3、查找第一个和最后一个匹配元素

有时我们需要查找数组中第一个或最后一个匹配的元素，这可以通过修改标准的二分查找实现。

1）查找第一个匹配元素

#include <stdio.h>

// 查找第一个匹配元素
int binarySearchFirstOccurrence(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            result = mid;
            right = mid - 1;  // 继续向左搜索
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

int main() {
    int arr[] = {2, 3, 3, 3, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 3;
    int result = binarySearchFirstOccurrence(arr, n, target);
    if (result == -1)
        printf("Element is not present in array\n");
    else
        printf("Element is present at index %d\n", result);
    return 0;
}

2）查找最后一个匹配元素

#include <stdio.h>

// 查找最后一个匹配元素
int binarySearchLastOccurrence(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            result = mid;
            left = mid + 1;  // 继续向右搜索
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

int main() {
    int arr[] = {2, 3, 3, 3, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 3;
    int result = binarySearchLastOccurrence(arr, n, target);
    if (result == -1)
        printf("Element is not present in array\n");
    else
        printf("Element is present at index %d\n", result);
    return 0;
}