用递归函数实现二分查找

设计一个递归算法，实现对顺序查找表ST中key为k的二分查找,，表的长度为n；算法头给定：int binsearch(stable *ST,int low,int high，int k)

根据k与表值的比较，递归进行二分查找

#include <stdio.h>
#define MAXSIZE 1000
typedef struct _stable
{
    int length;
    int data[MAXSIZE];
}stable;
int binsearch(stable *ST,int low,int high，int k)
{
    if(low > high)
        return -1;
    int mid = (low+high)/2;
    if(ST[mid]==k)
        return mid;
    if(ST[mid] >k)
        return binsearch(ST,low,mid-1,k);
    return binsearch(ST,mid+1,high,k);
}
int main()
{
    stable st;
    scanf("%d",&st.length);
    for(int i=0;i<st.length;i++)
        scanf("%d",&st.data[i]);
    int k;
    scanf("%d",&k);
    int idx = binsearch(&st,0,st.length-1,k);
    printf("%d",idx);
}

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 以下回答来自chatgpt:

  def binary_search(ST: list[int], low: int, high: int, k: int) -> int:
      """
      递归实现二分查找算法
      :param ST: 顺序查找表
      :param low: 查找范围最小下标
      :param high: 查找范围最大下标
      :param k: 目标值
      :return: 如果找到目标值，则返回其下标；如果没有找到，则返回-1
      """
      if low > high:
          return -1  # 查找失败，返回-1
      mid = (low + high) // 2
      if ST[mid] == k:
          return mid  # 找到目标值，返回下标
      elif ST[mid] < k:
          return binary_search(ST, mid + 1, high, k)  # 在右半部分继续查找
      else:
          return binary_search(ST, low, mid - 1, k)  # 在左半部分继续查找
  

  解释说明：

  1. 首先定义一个递归函数binary_search，该函数参数包括顺序查找表ST、查找范围最小下标low、查找范围最大下标high以及目标值k；
  2. 如果查找范围的最小下标low大于最大下标high，那么说明查找失败，此时返回-1。
  3. 如果查找范围的中间位置的值等于目标值k，那么说明找到了目标值，此时返回中间位置的下标mid。
  4. 如果中间位置的值小于目标值k，那么说明在右半部分查找，此时递归调用binary_search函数，查找右半部分；
  5. 如果中间位置的值大于目标值k，那么说明在左半部分查找，此时递归调用binary_search函数，查找左半部分；
  6. 最终如果没有找到目标值，那么最终返回-1。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^