2写一个三分检索程序,首先检查n/3的元素是否等于某个x的值,然后检查2n/3处的元素,这样,或者找到或者把集合缩小到原来的1/3.找到输出元素下标,否则输出-1.
时间: 2024-02-28 10:53:14 浏览: 19
以下是一个简单的三分查找程序的实现,可以实现上述功能:
```python
def ternary_search(arr, x):
left, right = 0, len(arr) - 1
while right >= left:
# Find the first pivot
mid1 = left + (right - left) // 3
# Find the second pivot
mid2 = right - (right - left) // 3
# Check if x is present at mid1
if arr[mid1] == x:
return mid1
# Check if x is present at mid2
if arr[mid2] == x:
return mid2
# If x is smaller than mid1, ignore right third
if x < arr[mid1]:
right = mid1 - 1
# If x is greater than mid2, ignore left third
elif x > arr[mid2]:
left = mid2 + 1
# Otherwise, search the middle third
else:
left = mid1 + 1
right = mid2 - 1
# If we reach here, then the element was not present
return -1
```
这个函数接受一个数组和一个要查找的值x作为参数,并返回x在数组中的下标,如果x不存在于数组中,则返回-1。该算法的时间复杂度为O(log3 n)。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)