给定一个有序表或从键盘上输入一组有序的序列,用折半查找方法查找出某个数是否存在,如果存在,请给出其在有序表中的位置,否则给出查找不成功的提示。
时间: 2023-12-05 20:03:36 浏览: 38
折半查找(Binary Search)也叫二分查找,是一种在有序数组中查找特定元素的搜索算法。
具体实现如下:
1. 定义左右两个指针,分别指向数组的第一个元素和最后一个元素。
2. 取数组中间位置的元素,与目标元素进行比较。
3. 如果中间元素等于目标元素,则找到目标元素,返回它在数组中的位置。
4. 如果中间元素大于目标元素,则目标元素在左半部分,将右指针移动到中间位置的左侧。
5. 如果中间元素小于目标元素,则目标元素在右半部分,将左指针移动到中间位置的右侧。
6. 重复以上步骤,直到找到目标元素或者左右指针重合,表示未找到目标元素。
以下是具体的 Python 代码实现:
```python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1 # 找不到目标元素
# 示例
arr = [1, 3, 5, 7, 9]
target = 5
index = binary_search(arr, target)
if index != -1:
print("目标元素在数组中的位置是:", index)
else:
print("未找到目标元素")
```
输出结果:
```
目标元素在数组中的位置是: 2
```