写出代码:在一个给定的n个元素的有序序列中查找出与给定关键字x相同的元素的具体位置。即输入一个n个元素的序列,其中n个元素从小到大的顺序排列,查找是否存在给定的值x.(用二分查找法)。
时间: 2024-09-11 15:05:30 浏览: 37
数据结构期末考试试题与答案.doc
二分查找是一种高效的查找算法,适用于已排序的序列。其基本思想是在有序序列中,每次取中间位置的元素与关键字x进行比较,如果相等则查找成功;如果关键字x小于中间位置的元素,则在左半部分继续查找;如果关键字x大于中间位置的元素,则在右半部分继续查找,直到找到或者子序列为空为止。
以下是使用Python实现的二分查找算法代码示例:
```python
def binary_search(sorted_list, x):
left, right = 0, len(sorted_list) - 1
while left <= right:
mid = (left + right) // 2
if sorted_list[mid] == x:
return mid # 找到x,返回位置索引
elif sorted_list[mid] < x:
left = mid + 1 # 在右半部分查找
else:
right = mid - 1 # 在左半部分查找
return -1 # 未找到x,返回-1
# 示例用法
n = 10
sorted_list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
x = 7
position = binary_search(sorted_list, x)
if position != -1:
print(f"元素{x}在序列中的位置为: {position}")
else:
print(f"序列中不存在元素{x}")
```
阅读全文