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)，适用于有序表中查找一个元素或者确定一个元素是否存在。