搜索算法

Linear Search(线性搜索)

问题： 给定一个有n个元素的数组，写一个函数在数组中搜索给定元素。

Java实现

class LinearSearch
{
    // This function returns index of element x in arr[]
    static int search(int arr[], int n, int x)
    {
        for (int i = 0; i < n; i++)
        {
            // Return the index of the element if the element
            // is found
            if (arr[i] == x)
                return i;
        }

        // return -1 if the element is not found
        return -1;
    }
}

时间复杂度：$O\left( n\right)$

Binary Search(二分查找)

问题： 给定一个有n个元素的有序数组，写一个函数在数组中搜索给定元素。

Java实现

// Java implementation of recursive Binary Search
class BinarySearch
{
    // Returns index of x if it is present in arr[l..
    // r], else return -1
    int binarySearch(int arr[], int l, int r, int x)
    {
        if (r>=l)
        {
            int mid = l + (r - l)/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, l, mid-1, x);

            // Else the element can only be present
            // in right subarray
            return binarySearch(arr, mid+1, r, x);
        }

        // We reach here when element is not present
        //  in array
        return -1;
    }

    // Driver method to test above
    public static void main(String args[])
    {
        BinarySearch ob = new BinarySearch();
        int arr[] = {2,3,4,10,40};
        int n = arr.length;
        int x = 10;
        int result = ob.binarySearch(arr,0,n-1,x);
        if (result == -1)
            System.out.println("Element not present");
        else
            System.out.println("Element found at index " +
                                                 result);
    }
}

时间复杂度：$O\left( \log n\right)$

适用场景：有序

Jump Search(跳跃搜索)

Jump Search是用于有序数组的搜索算法。基本思想是通过以固定步长向前跳跃或跳过一些元素来代替搜索所有元素来检查更少的元素(而不是线性搜索)。

例如，假设我们有一个大小为n的数组arr[]和大小为m的块（将被跳转）。然后我们搜索索引arr [0]，arr[m]，arr[2m] … …arr[km]等等。一旦我们找到了间隔(arr[km] < x <arr [(k + 1)m])，我们就从索引km开始执行线性搜索操作来查找元素x。

什么是最佳跳跃步长?

在最坏的情况下，我们必须进行n/m跳转，并且如果最后一次选中的值大于要搜索的元素，我们将对线性搜索进行m-1比较。因此，最坏情况下的比较总数将是((n/m)+ m-1)。当m =√n时，函数的值((n/m)+m-1)最小。因此，最好的步长是m=√n。

Java实现

// Java program to implement Jump Search.
public class JumpSearch
{
    public static int jumpSearch(int[] arr, int x)
    {
        int n = arr.length;

        // Finding block size to be jumped
        int step = (int)Math.floor(Math.sqrt(n));

        // Finding the block where element is
        // present (if it is present)
        int prev = 0;
        while (arr[Math.min(step, n)-1] < x)
        {
            prev = step;
            step += (int)Math.floor(Math.sqrt(n));
            if (prev >= n)
                return -1;
        }

        // Doing a linear search for x in block
        // beginning with prev.
        while (arr[prev] < x)
        {
            prev++;

            // If we reached next block or end of
            // array, element is not present.
            if (prev == Math.min(step, n))
                return -1;
        }

        // If element is found
        if (arr[prev] == x)
            return prev;

        return -1;
    }

    // Driver program to test function
    public static void main(String [ ] args)
    {
        int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
                     34, 55, 89, 144, 233, 377, 610};
        int x = 55;

        // Find the index of 'x' using Jump Search
        int index = jumpSearch(arr, x);

        // Print the index where 'x' is located
        System.out.println("\nNumber " + x +
                            " is at index " + index);
    }
}

时间复杂度：$O\left( \sqrt {n}\right)$

适用场景：有序

Binary Search优于Jump Search，但Jump Search有一个优势，即我们只返回一次(Binary Search可能需要高达O(Log n)个跳转)。因此，在跳回成本高昂的系统中，我们使用Jump Search。

Interpolation Search(插值搜索)

给定一个有n个均匀分布值值的有序数组，编写一个函数来搜索数组中的特定元素。

插值搜索是对二分搜索的改进，其中排序数组中的值均匀分布。二分查找总是对中间元素进行检查。插值搜索可能会根据正在搜索的值进入不同的位置。例如，如果搜索的值更接近最后一个元素，则插值搜索可能会从结尾开始搜索。

要找到要搜索的位置，它使用以下公式。

公式的想法当要搜索的元素更接近arr[hi]，则返回较大的pos值，
如果要搜索的元素更接近[lo]，则返回较小的pos值。
pos = lo + [(x-arr[lo])*(hi-lo)/(arr[hi]-arr[Lo])]

arr[] ==> Array where elements need to be searched
x     ==> Element to be searched
lo    ==> Starting index in arr[]
hi    ==> Ending index in arr[]

Java实现

// Java program to implement interpolation search

class InterpolationSearch
{
    // Array of items on which search will
    // be conducted.
    static int arr[] = new int[]{10, 12, 13, 16, 18, 19, 20, 21, 22, 23,
                                         24, 33, 35, 42, 47};

    // If x is present in arr[0..n-1], then returns
    // index of it, else returns -1.
    public static int interpolationSearch(int x)
    {
        // Find indexes of two corners
        int lo = 0, hi = (arr.length - 1);

        // Since array is sorted, an element present
        // in array must be in range defined by corner
        while (lo <= hi && x >= arr[lo] && x <= arr[hi])
        {
            // Probing the position with keeping
            // uniform distribution in mind.
            int pos = lo + (((hi-lo) /
                  (arr[hi]-arr[lo]))*(x - arr[lo]));

            // Condition of target found
            if (arr[pos] == x)
                return pos;

            // If x is larger, x is in upper part
            if (arr[pos] < x)
                lo = pos + 1;

            // If x is smaller, x is in lower part
            else
                hi = pos - 1;
        }
        return -1;
    }

    // Driver method
    public static void main(String[] args)
    {
         int x = 18; // Element to be searched
         int index = interpolationSearch(x);

         // If element was found
         if (index != -1)
            System.out.println("Element found at index " + index);
         else
            System.out.println("Element not found.");
    }
}

时间复杂度：$O\left( \log \log n\right)$

适用场景：有序、均匀分布

Exponential Search(指数搜索)

指数搜索涉及两个步骤：(1)查找元素存在的范围；(2)在上面找到的范围中进行二分查找。

如何找到元素可能存在的范围？

这个想法是从子数组大小1开始，比较它的最后一个元素和x，然后尝试大小2，然后是4，直到子数组的最后一个元素不会更大。 一旦我们找到了一个索引i（在重复了i次之后），我们知道该元素必须存在于i / 2和i之间（为什么是i / 2？因为我们在以前的迭代中找不到更大的值）

Java实现

// Java     program to find an element x in a
// sorted array using Exponential search.

import java.util.Arrays;

class ExponentialSearch
{
    // Returns position of first ocurrence of
    // x in array
    public static int exponentialSearch(int arr[], int n, int x)
    {
        // If x is present at firt location itself
        if (arr[0] == x)
            return 0;

        // Find range for binary search by
        // repeated doubling
        int i = 1;
        while (i < n && arr[i] <= x)
            i = i*2;

        //  Call binary search for the found range.
        return Arrays.binarySearch(arr, i/2, Math.min(i, n), x);
    }

    // Driver method
    public static void main(String args[])
    {
        int arr[] = {2, 3, 4, 10, 40};
        int x = 10;
        int result = exponentialSearch(arr, arr.length, x);

        System.out.println((result < 0) ? "Element is not present in array" :
                                   "Element is present at index " + result);
    }
}

时间复杂度：$O\left( \log n\right)$

适用场景：有序

当目标元素更靠近开始位置时，Exponential Search优于Binary Search。