c - 二分搜索算法

Question

我已经实现了二进制搜索，代码如下，但我想编辑代码以便它也打印算法的历史

例如：初始数组：1 1 2 4 4 5 目标元素：3 搜索历史：2(2) 4(4) 无目标

#include <stdio.h>

int search(int array[], int x, int low, int high);

int main(void)
{
    int array[] = {1, 1, 2, 4, 4, 5};
    int n = sizeof(array) / sizeof(array[0]);

    int x = 3;

    printf("Initial array:\n");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");

    printf("Target element: %d\n", x);

    int result = search(array, x, 0, n - 1);

    (result == -1) ? printf("No targets\n") : printf("Element found at index %d\n", result);
}

int search(int array[], int x, int low, int high)
{
    if (high >= low)
    {
        int mid = low + (high - low) / 2;

        if (array[mid] == x)
        {
            return mid;
        }

        if (array[mid] > x)
            return search(array, x, low, high - 1);
        else
            return search(array, x, low + 1, high);
    }

    return -1;
}

标签： calgorithmsearchdata-structures

Answer 1

好吧，即使我不清楚这个问题是什么意思history of algorithm，但我假设您想打印您的算法未能获得密钥的次数（次数）。

如果我猜对了，你可以使用一个额外的变量来保存数字，你的算法会错过命中（或键）。

#include <stdio.h>


int search(int array[], int x, int low, int high, int failed);

int main(void)
{
int array[] = {1, 1, 2, 4, 4, 5};
int n = sizeof(array) / sizeof(array[0]);

int x = 5;
int failed = 0;
printf("Initial array:\n");
for (int i = 0; i < n; i++)
{
    printf("%d ", array[i]);
}
printf("\n");

printf("Target element: %d\n", x);

int result = search(array, x, 0, n - 1, failed);

(result == -1) ? printf("No targets\n") : printf("Element found at index %d\n", result);
}

int search(int array[], int x, int low, int high, int failed)
{
if (high >= low)
{
    int mid = low + (high - low) / 2;

    if (array[mid] == x)
    {
        return mid;
    }else{
        // number of times you, failed to hit the key (item to be searched)
        failed += 1;
        printf("%i(%i) ", failed, array[mid]);
    }

    if (array[mid] > x)
        return search(array, x, low, high - 1, failed);
    else
        return search(array, x, low + 1, high, failed);
}

return -1;
}