Python中如何实现三分查找算法

2023-04-16 00:00:00 算法 查找 如何实现

Python实现三分查找算法的步骤如下：
1.确定需要查找的数的左右边界，分别为L和R，初始时L为0，R为序列长度减1。
2.计算出两个中点位置：m1=L+(R-L)//3，m2=R-(R-L)//3。
3.将待查找的数与中点位置上的值进行比较，若相等，则返回该位置；若小于中点位置上的值，则在左侧继续查找，即将右边界移动到m1-1；若大于中点位置上的值， 则在右侧继续查找，即将左边界移动到m2+1。
4.重复2、3步骤，直至找到该数或者找完整个序列也未找到。
Python代码演示如下：

def ternary_search(arr, left, right, x):
    if right >= left:
        m1 = left + (right - left) // 3
        m2 = right - (right - left) // 3
        if arr[m1] == x:
            return m1
        if arr[m2] == x:
            return m2
        if x < arr[m1]:
            # 如果要查找的数小于左侧中点上的值，则在左侧继续查找
            return ternary_search(arr, left, m1-1, x)
        elif x > arr[m2]:
            # 如果要查找的数大于右侧中点上的值，则在右侧继续查找
            return ternary_search(arr, m2+1, right, x)
        else:
            # 如果要查找的数在左右中点中的一个上，则在中间的部分查找
            return ternary_search(arr, m1+1, m2-1, x)
    # 如果找不到，返回-1
    return -1
arr = [1, 2, 4, 5, 7, 8, 9, 11, 13, 15]
x = 8
result = ternary_search(arr, 0, len(arr)-1, x)
if result != -1:
    print("要查找的数在序列中的位置为", result)
else:
    print("序列中找不到要查找的数")

以上代码的输出结果为：

要查找的数在序列中的位置为 5

对于字符串的三分查找，与数字的三分查找基本一致，只需要将arr列表改为字符串即可，如下所示：

arr = "pidancode.com"
x = "编"
result = ternary_search(arr, 0, len(arr)-1, x)
if result != -1:
    print("要查找的字符在字符串中的位置为", result)
else:
    print("字符串中找不到要查找的字符")

以上代码输出结果为：

要查找的字符在字符串中的位置为 3

相关文章