写出有序表折半查找的递归算法代码c

下面是有序表折半查找的递归算法代码C语言实现：

int binarySearch(int arr[], int left, int right, int target) {
    if (left > right) {
        return -1; // 如果左边界大于右边界，说明查找失败
    }
    int mid = (left + right) / 2; // 计算中间位置
    if (arr[mid] == target) {
        return mid; // 如果中间位置的值等于目标值，说明查找成功
    } else if (arr[mid] > target) {
        return binarySearch(arr, left, mid - 1, target); // 如果中间位置的值大于目标值，说明目标值在左半部分
    } else {
        return binarySearch(arr, mid + 1, right, target); // 如果中间位置的值小于目标值，说明目标值在右半部分
    }
}

这段代码中，我们通过递归的方式实现了有序表折半查找。首先，我们判断左边界是否大于右边界，如果是的话，说明查找失败，返回-1。然后，我们计算中间位置，如果中间位置的值等于目标值，说明查找成功，返回中间位置。如果中间位置的值大于目标值，说明目标值在左半部分，我们对左半部分递归调用该函数。如果中间位置的值小于目标值，说明目标值在右半部分，我们对右半部分递归调用该函数。

相关问题

1.折半查找\n【问题描述】请写一非递归算法，该算法在按值严格递增排列的顺序表a[1..n]中采用折半查找法查找值不小于item的最小元素。若表中存在这样的元素，则算法给出该最小元素在表中的位置，否则，

### 回答1：
返回。

【算法思路】折半查找是一种高效的查找算法，它利用了有序表的特点，每次将查找区间折半，缩小查找范围，直到找到目标元素或者查找区间为空。具体实现时，可以用两个指针left和right分别指向查找区间的左右端点，然后计算中间位置mid，比较a[mid]和item的大小关系，如果a[mid]>=item，则说明目标元素在左半区间，将right指向mid-1；否则，目标元素在右半区间，将left指向mid+1。不断缩小查找区间，直到left>right为止。

【算法实现】以下是折半查找的非递归实现代码：

int binarySearch(int a[], int n, int item) {
int left = 1, right = n, mid;
while (left <= right) {
mid = (left + right) / 2;
if (a[mid] >= item) {
if (mid == 1 || a[mid-1] < item) {
return mid;
} else {
right = mid - 1;
}
} else {
left = mid + 1;
}
}
return ;
}

其中，a[]表示有序表，n表示表的长度，item表示要查找的元素。如果找到了目标元素，则返回它在表中的位置；否则，返回。

### 回答2：
折半查找，也称二分查找，是一种常见的查找算法。该算法是利用已排序的列表，将列表分成两半进行查找，以便将搜索范围减半，从而提高查找效率。在查找时，先确定列表中间位置的元素的值，如果该值大于待查元素，则在列表的前半段进行查找；否则在列表的后半段进行查找，每次都将查找范围缩小一半，直到找到目标元素为止。

以下是折半查找的非递归算法：

1. 定义函数binarySearch，参数为一个严格递增的顺序表a[1..n]和目标元素item，返回值为目标元素的位置。

2. 初始化变量low=1和high=n。

3. 如果low>high，则返回0，表示未找到目标元素。

4. 用变量mid记录low和high的中间位置（mid=(low+high)/2）。

5. 如果列表的第mid个元素等于目标元素item，则返回mid。

6. 如果列表的第mid个元素大于目标元素item，则在高半段进行查找，即让high=mid-1，返回步骤3。

7. 如果列表的第mid个元素小于目标元素item，则在低半段进行查找，即让low=mid+1，返回步骤3。

8. 程序结束。

对于题目中要求找到不小于item的最小元素，可以将步骤5改为查找第一个大于等于item的元素，即判断列表的第mid个元素是否大于等于item，如果是，则继续在低半段进行查找，否则在高半段进行查找。在找到第一个大于等于item的元素后，可以继续判断其前一个元素是否小于item，如果是，则返回第一个大于等于item的元素的位置，否则返回0，表示未找到目标元素。

### 回答3：
折半查找是一种高效的查找算法。在按值递增排列的有序表中查找一个元素时，可以采用折半查找。其基本思想是不断缩小查找范围，将待查找的序列分成两半，每次比较中间位置的值与待查找元素的大小关系，然后根据查找元素与整个序列的大小关系，选择新的查找区间，直至找到要查找的元素或者确定不存在该元素。

下面是非递归算法的步骤：

1. 定义left=1，right=n。

2. 执行二分查找，即：

- 如果left>right，则该元素不存在，返回-1。

- 计算mid=(left+right)/2。

- 如果a[mid]>=item，则在左半部分继续查找，令right=mid-1。

- 如果a[mid]<item，则在右半部分继续查找，令left=mid+1。

3. 当left<=right时，最终找到了第一个不小于item的元素，返回该元素的下标left。

4. 算法结束。

例如，对于有序表a[1..n]={1,3,5,7,9,11,13,15,17,19}，查找元素item=8，使用折半查找算法，具体步骤如下：

1. 定义left=1，right=10。

2. 执行二分查找：

- mid= (left+right)/2=5，a[mid]=9>8，则在左半部分继续查找，令right=mid-1=4。

- mid=(left+right)/2=2，a[mid]=3<8，则在右半部分继续查找，令left=mid+1=3。

- mid=(left+right)/2=4，a[mid]=7<8，则在右半部分继续查找，令left=mid+1=5。

3. 因为left<=right，最终找到了第一个不小于8的元素a[left]=9，在表中的位置为5。

4. 算法结束。

综上所述，折半查找是一种高效的查找算法，其时间复杂度为O(logn)，适用于有序表中查找一个元素或者确定一个元素是否存在。

对关键字序列{21，34，56，78，99，100，102，109，200} 分别进行折半查找109，20。 请选择： 1. 根据算法步骤写出查找过程，列举查找过程中带查找序列和上限下限，中间值并画出有序表进行二分查找的判定树。 2. 编程实现查找过程和结果并画出有序表进行二分查找的判定树。 注意：1和2中请选择一个方式进行查找算法练习。

1. 折半查找的算法步骤如下：

- 将待查找序列按照关键字大小升序排列。
- 初始化上限`high`为序列末尾的下标，下限`low`为序列开头的下标。
- 当`low<=high`时，重复以下步骤：
- 计算中间位置`mid=(low+high)/2`。
- 如果待查找关键字等于中间位置的关键字，则返回该位置。
- 如果待查找关键字小于中间位置的关键字，则在上半部分继续查找，将`high`更新为`mid-1`。
- 如果待查找关键字大于中间位置的关键字，则在下半部分继续查找，将`low`更新为`mid+1`。
- 如果待查找关键字不在序列中，则返回不存在的标记。

对于关键字序列{21，34，56，78，99，100，102，109，200}，折半查找109的过程如下：

- 初始时，`low=0`，`high=8`，`mid=(0+8)/2=4`。
- 中间位置的关键字为99，109大于99，故在上半部分继续查找。
- 更新`high=mid-1=3`，`mid=(0+3)/2=1`。
- 中间位置的关键字为34，109大于34，故在上半部分继续查找。
- 更新`high=mid-1=0`，`mid=(0+0)/2=0`。
- 中间位置的关键字为21，109大于21，故在上半部分继续查找。
- 更新`high=mid-1=-1`，退出查找。109在序列中，返回该位置3。

折半查找20的过程如下：

- 初始时，`low=0`，`high=8`，`mid=(0+8)/2=4`。
- 中间位置的关键字为99，20小于99，故在下半部分继续查找。
- 更新`low=mid+1=5`，`high=8`，`mid=(5+8)/2=6`。
- 中间位置的关键字为102，20小于102，故在下半部分继续查找。
- 更新`low=mid+1=7`，`high=8`，`mid=(7+8)/2=7`。
- 中间位置的关键字为109，20小于109，故在下半部分继续查找。
- 更新`low=mid+1=8`，退出查找。20不在序列中，返回不存在的标记。

2. 以下是Python语言实现折半查找的代码，以及查找过程的判定树。在代码中，使用了递归方式实现查找过程。

def binarySearch(seq, low, high, key):
    if low > high:
        return -1 # 不存在
    mid = (low + high) // 2
    if seq[mid] == key:
        return mid # 找到关键字
    elif seq[mid] > key:
        return binarySearch(seq, low, mid-1, key) # 在下半部分查找
    else:
        return binarySearch(seq, mid+1, high, key) # 在上半部分查找

seq = [21, 34, 56, 78, 99, 100, 102, 109, 200]
key1 = 109
key2 = 20

print("查找{}的结果：{}".format(key1, binarySearch(seq, 0, len(seq)-1, key1)))
print("查找{}的结果：{}".format(key2, binarySearch(seq, 0, len(seq)-1, key2)))

判定树如下：

      99
     /  \
    /    \
  34      102
 /  \     /  \
/    \   /    \
21    56 100  109
      /         \
     /           \
    78          200

在判定树中，每个非叶子节点都表示一次比较操作。从根节点开始，如果待查找关键字小于节点的关键字，则向左子树查找；如果待查找关键字大于节点的关键字，则向右子树查找。叶子节点表示查找结束时的结果。