二分搜索算法c 语言

二分搜索算法是一种在一个已按非降序排序的序列中查找某一特定元素的搜索算法。它的主要功能是在一个已按非降序排序的序列中，查找是否存在一个元素key，如果存在，返回该元素的索引值，否则返回-1。二分搜索算法的基本思想是将待查序列分成两部分，取中间位置的元素与目标元素进行比较，如果相等则返回该元素的索引值，如果目标元素小于中间位置的元素，则在左半部分继续查找，否则在右半部分继续查找，直到找到目标元素或者待查序列为空。二分搜索算法的时间复杂度为O(log n)。

在C语言中，可以使用以下代码实现二分搜索算法：

int binarySearch(int arr[], int low, int high, int key) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

其中，arr为待查序列，low和high分别为序列的起始位置和结束位置，key为目标元素。函数返回目标元素的索引值，如果不存在则返回-1。

相关问题

实现二分查找算法 c

下面是一个使用二分查找算法在 C 语言中查找给定元素的示例代码：

#include <stdio.h>

int binarySearch(int arr[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x)
            return mid;
        else if (arr[mid] < x)
            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 x = 10;
    int result = binarySearch(arr, n, x);
    if (result == -1)
        printf("元素不在数组中");
    else
        printf("元素在数组中的索引：%d", result);
    return 0;
}

在上面的示例代码中，我们首先定义了一个 `binarySearch` 函数，用于在给定数组中查找指定元素。这个函数接受三个参数：要查找的数组 `arr`、数组的长度 `n`、要查找的元素 `x`。

函数中使用了一个循环来不断地缩小查找范围。循环条件是 `left <= right`，即只要左边的索引小于等于右边的索引，就继续查找。在每次循环中，我们先计算出中间元素的索引 `mid`，然后判断这个中间元素是否等于要查找的元素。如果相等，直接返回中间元素的索引；如果中间元素小于要查找的元素，则继续在右边的子数组中查找；否则，在左边的子数组中查找。

最后，我们在 `main` 函数中定义了一个数组 `arr`，然后调用 `binarySearch` 函数来查找元素 `10` 在数组中的索引。如果函数返回 `-1`，则表示元素不在数组中；否则，返回的就是元素在数组中的索引。

C语言代码实现二分插入排序算法

下面是用 C 语言实现二分插入排序算法的代码示例：

#include <stdio.h>

void binaryInsertionSort(int arr[], int n) {
    int i, j, key, low, high, mid;
    for (i = 1; i < n; i++) {
        key = arr[i];
        low = 0;
        high = i - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (key < arr[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (j = i - 1; j >= low; j--)
            arr[j + 1] = arr[j];
        arr[low] = key;
    }
}

int main() {
    int arr[] = {5, 2, 8, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    
    binaryInsertionSort(arr, n);
    
    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    
    return 0;
}

这段代码实现了二分插入排序算法，通过调用 `binaryInsertionSort` 函数将数组按升序排序。在 `main` 函数中，我们定义了一个整数数组 `arr`，然后计算数组的长度 `n`。接着，我们打印原始数组，调用 `binaryInsertionSort` 函数对数组进行排序，并最后打印排序后的数组。

运行这段代码，输出结果如下：

Original array: 5 2 8 3 1
Sorted array: 1 2 3 5 8

可以看到，原始数组经过二分插入排序后得到了升序排序的结果。