用python写一个折半查找法
时间: 2023-11-20 08:38:23 浏览: 68
可以的,以下是用Python实现折半查找法的代码:
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
注意,以上代码仅供参考,具体实现需要根据具体需求进行调整。
相关问题
编写函数实现折半查找Python
折半查找(Binary Search)是一种常用的查找法,它适用于有序数组。下面是用Python编写实现折半查找的函数:
```python
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
```
这个函数接受两个参数,一个是有序数组 `arr`,另一个是要查找的目标值 `target`。函数使用两个指针 `low` 和 `high` 来表示查找范围的左右边界。在每次循环中,计算中间位置 `mid`,然后将目标值与中间位置的元素进行比较。如果相等,则返回中间位置;如果目标值小于中间位置的元素,则在左半部分继续查找;如果目标值大于中间位置的元素,则在右半部分继续查找。如果最终没有找到目标值,则返回 -1。
用python编写一个程序:输出在顺序表(1,2,3,4,5,6,7,8,9中采用折半查找法查找关键字9的过程)
下面是用Python代码实现在顺序表中采用折半查找法查找关键字9的过程:
```python
def binary_search(seq, key):
low, high = 0, len(seq) - 1
while low <= high:
mid = (low + high) // 2
if seq[mid] < key:
low = mid + 1
elif seq[mid] > key:
high = mid - 1
else:
return mid
return -1
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
key = 9
index = binary_search(seq, key)
if index != -1:
print("关键字%d在顺序表中的位置是:%d" % (key, index))
else:
print("关键字%d不在顺序表中" % key)
```
输出结果为:
```
关键字9在顺序表中的位置是:8
```
解释:首先将待查找的序列按照顺序排列,即seq=[1, 2, 3, 4, 5, 6, 7, 8, 9],然后定义一个二分查找函数binary_search(seq, key),其中seq表示待查找的序列,key表示待查找的关键字。在函数中,首先初始化查找区间的起点low和终点high分别为0和len(seq)-1,然后利用while循环进行二分查找,即每次将查找区间折半,若中间位置的元素小于关键字,则在右半部分继续查找;若中间位置的元素大于关键字,则在左半部分继续查找;否则中间位置的元素等于关键字,查找成功,返回中间位置的下标。如果查找失败,则返回-1。最后,在主函数中调用binary_search函数,输出结果。