数据结构折半查找问题

在n个记录的有序顺序表中进行折半查找,查找过程落在对应判定树的第i层的某个外部结点中，则关键字的比较次数是
为什么不是i呀他在i层

i 是怎么使用的？每次折半时传 i 的地址并在折半方法里 *i++

帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7809884
这篇博客你也可以参考下：作物杂交作物杂交是作物栽培中重要的一步。已知有 N 种作物 (编号 1 至 N )，第 i 种作物从播种到成熟的时间为 Ti 。作物之间两两可以进行杂交，杂交时间取两种中时间
除此之外, 这篇博客: 数组循环左移问题,将一个N个元素的数组向左移i个位置中的 解法三: 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

AB(A代表前i个元素,B代表后n-i个元素),先将A置换,在将B置换,最后将AB置换
AB -> A^-1B -> A^-1B^-1 -> BA
算法如下:

#include <stdio.h>
void foreMove(int* a, int path, int n);
void reverse(int* a, int m, int n); 
int main(void){
	int a[7] = {3,5,7,9,11,13,66};
	int i;
	foreMove(a, 5, 7);
	for(i=0; i<7; i++){
		printf("%d ",a[i]);
	}
	return 0;
} 
void foreMove(int* a, int path, int n){
	reverse(a, 0, path-1);
	reverse(a, path, n-1);
	reverse(a, 0, n-1);
}
void reverse(int* a, int m, int n){
	int temp;
	while( m<n ){
		temp = *(a+m);
		*(a+m) = *(a+n);
		*(a+n) = temp;
		m++;
		n--;
	}
}

结果
在这里插入图片描述

需移动 i/2 + (n-i)/2 + n/2 = n 次数组单元
需1个临时交换存储单元

以下回答由chatgpt基于相关博客总结生成:
折半查找是一种常用的搜索算法，应用于对有序表进行查找。它通过比较中间位置关键字与查找关键字来确定下一步查找的区域，将查找区域缩小一半，直到找到目标为止。但是，如果查找过程落在对应判定树的第i层的某个外部结点中，关键字的比较次数应该是Log2（i+1）而不是i次。因为折半查找的搜索过程是不断将查找区域缩小一半，而不是对每个结点进行比较。具体的解决方案如下：
解决方案： 1. 折半查找算法折半查找算法实现如下：
```
int BinarySearch(int arr[], int left, int right, int x) {
    if(left > right) {
        return -1;
    }
    int mid = left + (right - left) / 2; //求中间位置
    if(arr[mid] == x) {
        return mid;
    } else if(arr[mid] > x) {
        return BinarySearch(arr, left, mid - 1, x);
    } else {
        return BinarySearch(arr, mid + 1, right, x);
    }
}
```
其中，left表示左边界，right表示右边界，x表示要查找的元素，mid表示中间位置。通过这个算法，可以快速查找到对应元素。
1. 查找过程的分析假设判定树的高度为k，则判定树的最后一层共有2^k个节点。中间节点与外部结点的比例为1:2，即判定树共有2^k-1个节点，其中外部结点数为2^(k-1)。通过归纳法，可以证明若查找过程停留在第i(1<=i<=k)层的某个节点，则该节点的编号为2^(i-1)+j，其中0<=j<=2^(i-1)-1，即该节点编号在2^(i-1)到2^i-1的范围内。转化成二进制，该节点编号的有效位数为i。
在折半查找中，每一次比较都会将待查区间缩小为原来的一半，因此需要的比较次数最多为判定树的深度k。对于普通的二叉查找树，其深度最差可达到n，而对于平衡二叉查找树，则可以对高度作出限制，将查找时间复杂度控制在Log2n以内。
因此，在折半查找中，如果查找过程落在对应判定树的第i层的某个外部结点中，则该节点编号的有效位数为i，因此需要进行Log2(i+1)次比较，而不是i次。
下面是对折半查找优化后的代码：
```
int BinarySearch(int arr[], int left, int right, int x) {
    if(left > right) {
        return -1;
    }
    int mid = left + (right - left) / 2; //求中间位置
    if(arr[mid] == x) {
        return mid;
    } else if(arr[mid] > x) {
        return BinarySearch(arr, left, mid - 1, x);
    } else {
        return BinarySearch(arr, mid + 1, right, x);
    }
}

int main() {
    int arr[] = {4, 7, 8, 9, 13, 15, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 13;
    int res = BinarySearch(arr, 0, n - 1, x);
    if(res == -1) {
        cout << "未找到元素" << endl;
    } else {
        cout << "元素" << x << "的位置为" << res << endl;
    }
    return 0;
}
```