gpt4 book ai didi

c - 二分查找中的结束索引

转载 作者:行者123 更新时间:2023-11-30 15:18:11 24 4
gpt4 key购买 nike

我有几个关于二分搜索的问题。

  1. 在下面的代码中,我从 main 传递 fun(array, 0, len-1)。传递“len”作为结束索引也可以吗?我认为没关系,也已经验证了答案。

我觉得唯一的区别是,数组中中间元素之后的部分会少一次计算,而中间元素之前的数组部分会增加一次计算。

  • 此外,在执行 mid = (s+e)/2 时,通常整数除法会取下限值。如果我们做 mid = (ceiling)(s+e)/2 呢?再说一次,我觉得唯一的区别是,在中间元素之后的数组部分将少一项计算,而在中间元素之前的数组部分将增加一项计算。
  • 下面是我的代码

    #include <stdio.h>    
    int key = 0;
    int len = 0;

    int main(void)
    {
    int a[] = {1,2,3,4,5,6,7,8,9};

    printf("Enter key : ");
    scanf("%d",&key);

    len = sizeof(a)/sizeof(*a) - 1;

    printf("Array : ",print(a));
    //printf("Element found at index : %d",fun(a,0,len-1));
    printf("Element found at index : %d",fun(a,0,len));

    printf("\n");
    return 0;
    }

    int fun(int a[], int s, int e)
    {
    int mid = 0;
    mid = (s+e)/2;

    if(a[mid] == key)
    return mid;

    if(s == e)
    return -1;

    if(a[mid] > key)
    fun(a,s,mid-1);
    else
    fun(a,mid+1,e);
    }
    int print(int a[])
    {
    int i = 0;
    for(i=0;i<len;i++)
    printf("%d ",a[i]);
    printf("\n");
    }

    最佳答案

    是的,传递lenlen-1只会改变递归调用的数量,对于mid元素之前的元素和mid元素之后的元素来说,它会有所不同元素。

    使用ceil也是如此。因此,是的,根据数组中的索引,不同元素的递归调用数量可能会有所不同。

    这两项更改都会给您正确的结果。

    关于c - 二分查找中的结束索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31622774/

    24 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com