用Python写一个三分检索程序,首先检查n/3的元素是否等于某个x的值,然后检查2n/3处的元素,这样,或者找到或者把集合缩小到原来的1/3.找到输出元素下标,否则输出-1.
时间: 2024-03-16 10:43:49 浏览: 64
下面是用Python实现的三分检索程序:
```python
def ternary_search(arr, x):
left = 0
right = len(arr) - 1
while left <= right:
mid1 = left + (right - left) // 3
mid2 = right - (right - left) // 3
if arr[mid1] == x:
return mid1
elif arr[mid2] == x:
return mid2
elif x < arr[mid1]:
right = mid1 - 1
elif x > arr[mid2]:
left = mid2 + 1
else:
left = mid1 + 1
right = mid2 - 1
return -1
# 示例
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
x = 7
index = ternary_search(arr, x)
if index == -1:
print("元素不存在")
else:
print("元素在数组中的下标为:", index)
```
其中,arr是待查找的有序数组,x是目标值。程序输出的结果为:
```
元素在数组中的下标为: 6
```
这说明元素7在数组arr中的下标为6。
阅读全文