介绍

三元搜索算法是计算机科学中用于查找 单峰函数 的最小值或最大值的一种技术。三元搜索确定最小值或最大值不能在域的前三分之一或不能在域的后三分之一，然后在剩余的三分之二上重复。三元搜索是分治算法的一个示例。

注意：数组需要进行排序才能对其进行三元搜索。

原理

执行三元搜索的步骤：

• 首先，我们将 key 与 mid1 的元素进行比较。如果发现相等，我们返回 mid1。
• 如果不是，那么我们将 key 与 mid2 的元素进行比较。如果发现相等，我们返回 mid2。
• 如果不是，那么我们检查 key 是否小于 mid1 的元素。如果是，则重复第一部分。
• 如果不是，那么我们检查 key 是否大于 mid2 处的元素。如果是，则重复到第三部分。
• 如果不是，那么我们回到第二（中间）部分。

实现

JavaScript

/* Ternary search is similar to binary search but it divide the sorted array
 * into three parts and determine which part the key lies in. The array will
 * be divided into three intervals by using two middle points, mid1 and mid2.
 * The value of the key will first compared with the two mid points, the value
 * will be returned if there is a match. Then, if the value of the key is less
 * than mid1, narrow the interval to the first part. Else, if the value of the
 * key is greater than mid2, narrow the interval to the third part. Otherwise,
 * narrow the interval to the middle part. Repeat the steps until the value is
 * found or the interval is empty(value not found after checking all elements).
 *
 * Reference: https://www.geeksforgeeks.org/ternary-search/
 */

function ternarySearchRecursive (arr, key, low = 0, high = arr.length - 1) {
  if (high >= low) {
    // find thmid1e mid1 and mid2
    const  = Math.floor(low + (high - low) / 3)
    const mid2 = Math.floor(high - (high - low) / 3)

    // check if key is found at any mid
    if (arr[mid1] === key) {
      // return index of key if found
      return mid1
    }
    if (arr[mid2] === key) {
      // return index of key if found
      return mid2
    }

    // since the key is not found at mid,
    // check in which region it is present
    // and repeat the Search operation
    // in that region
    if (key < arr[mid1]) {
      // the key lies in between low and mid1
      return ternarySearchRecursive(arr, key, low, mid1 - 1)
    } else if (key > arr[mid2]) {
      // the key lies in between mid2 and high
      return ternarySearchRecursive(arr, key, mid2 + 1, high)
    } else {
      // the key lies in between mid1 and mid2
      return ternarySearchRecursive(arr, key, mid1 + 1, mid2 - 1)
    }
  } else {
    // if low > high => we have searched the whole array without finding the item
    return -1
  }
}

function ternarySearchIterative (arr, key, low = 0, high = arr.length - 1) {
  while (high >= low) {
    // find the mid1 and mid2
    const mid1 = Math.floor(low + (high - low) / 3)
    const mid2 = Math.floor(high - (high - low) / 3)

    // check if key is found at any mid
    if (arr[mid1] === key) {
      // return index of key if found
      return mid1
    }
    if (arr[mid2] === key) {
      // return index of key if found
      return mid2
    }

    // since the key is not found at mid,
    // check in which region it is present
    // and repeat the Search operation
    // in that region
    if (key < arr[mid1]) {
      // the key lies in between low and mid1
      high = mid1 - 1
    } else if (key > arr[mid2]) {
      // the key lies in between mid2 and high
      low = mid2 + 1
    } else {
      // the key lies in between mid1 and mid2
      low = mid1 + 1
      high = mid2 - 1
    }
  }
  // the key was not found
  return -1
}

参考

• Ternary search - Wikipedia (opens new window)
• Ternary Search - GeeksforGeeks (opens new window)