在 C 中使用递归二进制搜索查找目标索引

Question

我只能使用给定的参数。一想到要找到目标的索引，我就无法思考。有什么想法吗？

#include <stdio.h>

int RecBinarySearch(int arr[], int len, int target) {

    if (len <= 0)
        return 0; 

    int mid = len/2;

    if (target == arr[mid]){
        return 1;
    }
    if (target < arr[mid]){
        int i=0;
        return RecBinarySearch(arr, mid, target);
    }

    else {
        return RecBinarySearch(arr+mid+1, len-mid-1, target);
    }
}

int main(void){
    int arr[6]={1,2,3,4,5,6};
    int len=sizeof(arr)/sizeof(arr[0]);
    int target = 5;
    RecBinarySearch(arr,len,target);
}

Answer 1

1st ：在这个目标中你真的不需要递归。您可能会更有效地用循环替换它，使用左右标记（由于各种原因，递归性非常昂贵）。

2nd ：而不是 returning 0 或 1，你不使用，你应该 return mid 或 -1 如果没有找到，并且因为你在递归中移动了你的数组call(传入array+mid+1)，应该把shift值加到return值上，然后在main.

中得到return值中的位置

Answer 2

Ideone link

#include <stdio.h>
int RecBinarySearch(int arr[], int len, int target) {
    if(len <= 0) return -1;
    int mid = len / 2;
    if(arr[mid] == target) return mid;
    if(arr[mid] < target) {
        int rightIndex = RecBinarySearch(arr+mid+1, len-mid-1, target);
        return rightIndex == -1 ? -1 : mid+rightIndex+1;
    } else {
        int leftIndex = RecBinarySearch(arr, mid, target);
        return leftIndex == -1 ? -1 : leftIndex;
    }
}

int main(void){
    int arr[6]={1,2,3,4,5,6};
    int len=sizeof(arr)/sizeof(arr[0]);
    int target = 5;
    printf("%d", RecBinarySearch(arr,len,target));
}

Answer 3

鉴于我只允许使用给定的参数，您可以使用以下方法。看到它工作 here:

int BinarySearch(int arr[], int len, int target) {
    int startI = 0, endI = len-1;

    while(startI<=endI)
    {
        int mid= (startI+endI)/2;
        if(arr[mid] == target)
            return mid;
        if(arr[mid] < target)
        {
            startI = mid +1;        
        }
        else
        {
            endI = mid -1;
        }
    }
    return -1;
}

在 C 中使用递归二进制搜索查找目标索引

Finding index of target using recursive binary search in C

c

recursion

binary-search