HUFEOJ-1594:A003顺序表：在有序数据中查找

金币值：1 定数：1 时间限制：1.000 s 内存限制：128 M

正确：6 提交：13 正确率：46.15% 命题人：

点赞量：0 收藏量：0 题目类型：程序知识点：顺序表，二分查找

设计并实现如下抽象数据类型，并在main函数测试。
ADT T{
数据对象:D={e₁,e₂,...,e₃₀|e_i均为正整数，其中e₁=2}
数据关系：S={<e_i,e_i+1>|1<i<30,e_i+1=e_i*2+1}
基本运算：
create(a[]):用D中的元素构建数组a
search(a[],x):利用折半查找的算法从a（a是D中的元素有序形成的数组）中查找某个数x，如果在其中则返回所在的数组下标，否则返回-1
}

1个整数

-1

二分查找（Binary Search），也称为折半查找，是一种在有序数组中查找特定元素的高效算法。其基本思想是将数组分成两部分，通过比较目标值与中间元素的大小关系，不断缩小查找范围，直到找到目标元素或确定目标元素不存在。详细模拟过程：

假设有一个有序数组 arr = [1, 3, 5, 7, 9, 11, 13]，要查找目标元素 target = 7。

1. 初始化

left = 0，指向数组的第一个元素。
right = len(arr) - 1 = 6，指向数组的最后一个元素。

2. 第一次循环

计算中间索引 mid = (left + right)/2 = (0 + 6) /2 = 3。
比较 arr[mid] 与 target 的大小：
- arr[3] = 7，target = 7，因为 arr[mid] == target，所以查找成功，返回 mid = 3。

另外一个模拟过程：

假设要查找目标元素 target = 8。

1. 初始化

left = 0，指向数组的第一个元素。
right = len(arr) - 1 = 6，指向数组的最后一个元素。

2. 第一次循环

计算中间索引 mid = (left + right)/2 = (0 + 6)/2 = 3。
比较 arr[mid] 与 target 的大小：
- arr[3] = 7，target = 8，因为 arr[mid] < target，所以更新 left = mid + 1 = 4。

3. 第二次循环

计算中间索引 mid = (left + right) / 2 = (4 + 6) / 2 = 5。
比较 arr[mid] 与 target 的大小：
- arr[5] = 11，target = 8，因为 arr[mid] > target，所以更新 right = mid - 1 = 4。

4. 第三次循环

计算中间索引 mid = (left + right) / 2 = (4 + 4) / 2 = 4。
比较 arr[mid] 与 target 的大小：
- arr[4] = 9，target = 8，因为 arr[mid] > target，所以更新 right = mid - 1 = 3。

5. 循环结束条件判断

此时 left = 4，right = 3，left > right，循环结束，返回 -1，表示目标元素不存在于数组中。

1594: A003顺序表：在有序数据中查找

题目描述

输入格式

输出格式

输入样例1 复制

输出样例1 复制

输入样例2 复制

输出样例2 复制

输入样例3 复制

输出样例3 复制

提示

1. 初始化

2. 第一次循环

1. 初始化

2. 第一次循环

3. 第二次循环

4. 第三次循环

5. 循环结束条件判断