查找算法--线性查找、二分查找和三分查找的原理及适用场景

特征：从第一个元素开始，采用逐个比较的方式进行查询，类似下图
前提：没有限制
使用场景：大部分场景，但性能低
时间复杂度： O(n)

特征：每次取中点进行判断，待查找集合减半；线性函数；不断逼近
前提：集合必须有序
适用场景：大部分场景
实现原理: 对于一个有序序列，每次选择中间的那个元素，与欲找出的元素进行比较，若比该元素大，则查找范围变为序列的前一半；反之，若中位元素比查找元素小，则将下一次的查找范围变为序列的后一半；若中位元素与想要查找的元素相等，返回中位元素在序列中的位置，查找成功。循环查找，就能找出想要查找的元素的位置。由此很容易想到利用递归的方法求解
时间复杂度：O(log₂ⁿ)

特征：每次取1/3处、2/3处进行判断，待查找集合减少2/3
前提：集合必须有序
适用场景： 对于单峰函数(先增后减或先减后增)，如果要求该函数在区间[Left,Right]上的极值点，可以采用三分的办法）
实现原理: 三分查找的原理和二分查找的原理基本相同，有所不同的是每次比较的不是中位元素，而是1/3处的元素和2/3处的元素。通过两次比价，将查找的范围缩减为原来的1/3，使查找效率提高。
时间复杂度：O(2log₃ⁿ)。2log₃ⁿ可以写成(2 / log₂³) * log₂ⁿ。由于(2 / log₂³)的值大于1，在最坏的情况下，三次查找比二次查找做更多的比较。

public class SimpleDemo {
    public static void main (String[] args) {
        int[] list = {1,2,3,4,5,6,7,8,9};
        System.out.println(lineSearch(list,5));
        System.out.println(binarySearch(list,5));
        System.out.println(ternarySearch(list,5));
    }

    
    public static int lineSearch(int arr[], int x) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (arr[i] == x) {
                return i;
            }
        }
        return -1;
    }

    
    public static int binarySearch(int arr[], int x){
        return binarySearch(arr,0,arr.length-1,x);
    }

    
    public static int binarySearch(int arr[], int start, int end, int x) {
        if (end >= start) {
            int mid = start + (end - start) / 2;

            // If the element is present at the
            // middle itself
            if (arr[mid] == x) {
                return mid;
            }

            // If element is smaller than mid, then
            // it can only be present in left subarray
            if (arr[mid] > x) {
                return binarySearch(arr, start, mid - 1, x);
            }
            // Else the element can only be present
            // in right subarray
            return binarySearch(arr, mid + 1, end, x);
        }
        return -1;
    }


    
    public static int ternarySearch(int arr[], int x) {
        return ternarySearch(arr,0,arr.length-1,x);
    }

    
    public static int ternarySearch(int arr[], int start, int end, int x) {
        if (end >= start) {
            int mid1 = start + (end - start) / 3;
            int mid2 = mid1 + (end - start) / 3;

            // If x is present at the mid1
            if (arr[mid1] == x) {
                return mid1;
            }

            // If x is present at the mid2
            if (arr[mid2] == x){
                return mid2;
            }

            // If x is present in left one-third
            if (arr[mid1] > x) {
                return ternarySearch(arr, start, mid1 - 1, x);
            }
            // If x is present in right one-third
            if (arr[mid2] < x) {
                return ternarySearch(arr, mid2 + 1, end, x);
            }
            // If x is present in middle one-third
            return ternarySearch(arr, mid1 + 1, mid2 - 1, x);
        }
        return -1;
    }
}