Search Algorithms in Java
Search Algorithms in Java
Introduction
Searching is one of the most common actions performed in regular business applications. This involves fetching some data stored in data structures like Arrays, List, Map, etc. More often than not, this search operation determines the responsiveness of the application for the end-user.
In this article, let's take a look at some of the searching strategies that can be used to cater to different scenarios. We will also implement them in Java and analyze their performance with some well-known parameters like Time and Space Complexity.

Linear Search
Binary Search
Knuth Morris Pratt Pattern Search
Jump Search
Interpolation Search
Exponential Search
Fibonacci Search
Java Collections API

Linear Search
Linear or Sequential Search is the simplest of search algorithms. While it most certainly is the simplest, it's most definitely not the most common, due to its inefficiency. It's a brute-force algorithm. Very rarely is it used in production, and in most cases, it's outperformed by other algorithms.
Linear Search has no prerequisites for the state of the underlying data structure.
Explanation
Linear Search involves sequential searching for an element in the given data structure until either the element is found or the end of the structure is reached.
If the element is found, we usually just return its position in the data structure. If not, we usually return -1.
Implementation
Now let's see how to implement Linear Search in Java:
public static int linearSearch(int arr[], int elementToSearch) {

    for (int index = 0; index < arr.length; index++) {
        if (arr[index] == elementToSearch)
            return index;
    }
    return -1;
}

To test it, we'll use a simple Array of integers:
int index = linearSearch(new int[]{89, 57, 91, 47, 95, 3, 27, 22, 67, 99}, 67);
print(67, index);

With a simple helper method to print the result:
public static void print(int elementToSearch, int index) {
    if (index == -1){
        System.out.println(elementToSearch + " not found.");
    }
    else {
        System.out.println(elementToSearch + " found at index: " + index);
    }
}

Output:
67 found at index: 8

Time Complexity
Here we are iterating through the entire set of N elements sequentially to get the location of the element being searched. The worst case for this algorithm will be if the element we are searching for is the last element in the array.
In this case, we will iterate N times before we find the element.
Hence, the Time Complexity of Linear search is O(N).
Space Complexity
This type of search requires only a single unit of memory to store the element being searched. This is not relevant to the size of the input Array.
Hence, the Space Complexity of Linear Search is O(1).
Applications
Linear Search can be used for searching in a small and unsorted set of data which is guaranteed not to increase in size by much.
It is a very basic search algorithm but due to its linear increase in time complexity, it does not find application in many production systems.
Binary Search
Binary or Logarithmic Search is one of the most commonly used search algorithms primarily due to its quick search time.
Explanation
This kind of search uses the Divide and Conquer methodology and requires the data set to be sorted beforehand.
It divides the input collection into equal halves, and with each iteration compares the goal element with the element in the middle.
If the element is found, the search ends. Else, we continue looking for the element by dividing and selecting the appropriate partition of the array, based on if the goal element is smaller or bigger than the middle element.
This is why it's important to have a sorted collection for Binary Search.
The search terminates when the firstIndex (our pointer) goes past lastIndex (last element), which implies we have searched the whole array and the element is not present.
There are two ways to implement this algorithm - iterative and recursive.
There shouldn't be a difference regarding time and space complexity between these two implementations, though this doesn't hold true to all languages.
Implementation
Iterative
Let's first take a look at the iterative approach:
public static int binarySearch(int arr[], int elementToSearch) {

    int firstIndex = 0;
    int lastIndex = arr.length - 1;

    // termination condition (element isn't present)
    while(firstIndex <= lastIndex) {
        int middleIndex = (firstIndex + lastIndex) / 2;
        // if the middle element is our goal element, return its index
        if (arr[middleIndex] == elementToSearch) {
            return middleIndex;
        }

        // if the middle element is smaller
        // point our index to the middle+1, taking the first half out of consideration
        else if (arr[middleIndex] < elementToSearch)
            firstIndex = middleIndex + 1;

        // if the middle element is bigger
        // point our index to the middle-1, taking the second half out of consideration
        else if (arr[middleIndex] > elementToSearch)
            lastIndex = middleIndex - 1;

    }
    return -1;
}

We can use the algorithm like this:
int index = binarySearch(new int[]{89, 57, 91, 47, 95, 3, 27, 22, 67, 99}, 67);
print(67, index);

Output:
67 found at index: 5

Recursive
And now let's take a look at the recursive implementation:
public static int recursiveBinarySearch(int arr[], int firstElement, int lastElement, int elementToSearch) {

    // termination condition
    if (lastElement >= firstElement) {
        int mid = firstElement + (lastElement - firstElement) / 2;

        // if the middle element is our goal element, return its index
        if (arr[mid] == elementToSearch)
            return mid;

        // if the middle element is bigger than the goal element
        // recursively call the method with narrowed data
        if (arr[mid] > elementToSearch)
            return recursiveBinarySearch(arr, firstElement, mid - 1, elementToSearch);

        // else, recursively call the method with narrowed data
        return recursiveBinarySearch(arr, mid + 1, lastElement, elementToSearch);
    }

    return -1;
}

The difference in the recursive approach is that we invoke the method itself once we get the new partition. In the iterative approach, whenever we determined the new partition we modified the first and last elements and repeated the process in the same loop.
Another difference here is that recursive calls are pushed on the method call-stack and they occupy one unit of space per recursive call.
We can use this algorithm like this:
int index = binarySearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 0, 10, 67);
print(67, index);

Output:
67 found at index: 5

Time Complexity
Since Binary Search divides the array into half each time its time complexity is O(log(N)). This time complexity is a marked improvement on the O(N) time complexity of Linear Search.
Space Complexity
This search requires only one unit of space to store the element to be searched. Hence, its space complexity is O(1).
If Binary Search is implemented recursively, it needs to store the call to the method on a stack. This may require O(log(N)) space in the worst case scenario.
Applications
It is the most commonly used search algorithm in most of the libraries for searching. The Binary Search tree is used by many data structures as well which store sorted data.
Binary Search is also implemented in Java APIs in the Arrays.binarySearch method.

            
                    
                        
                        
                    Link: For more details on the Binary Search algorithm, check out our detailed guide Binary Search in Java.
                
            Knuth Morris Pratt Pattern Search
As the name indicates, it is an algorithm for finding a pattern in the given text. This algorithm was developed by Donald Knuth, Vaughan Pratt, and James Morris, hence the name.
Explanation
In this search, the given pattern is first compiled. By compiling it, we try to find the prefix and suffix of the pattern string. This helps us when a mismatch happens - we will not start looking for the next match from the beginning of the index.
Instead, we skip the part of the text string which we have already compared and start comparing beyond that part. We determine this part by knowing the prefix and suffix so we are sure what part is already compared and can be safely skipped.
As a result of this skip, we can save a lot of comparisons and KMP performs faster than a naive brute-force algorithm.
Implementation
Let's create the compilePatternArray() method, which will be used later by the KMP search algorithm:
public static int[] compilePatternArray(String pattern) {
    int patternLength = pattern.length();
    int len = 0;
    int i = 1;
    int[] compliedPatternArray = new int[patternLength];
    compliedPatternArray[0] = 0;

    while (i < patternLength) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            len++;
            compliedPatternArray[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = compliedPatternArray[len - 1];
            } else {
                compliedPatternArray[i] = len;
                i++;
            }
        }
    }
    System.out.println("Compiled Pattern Array " + Arrays.toString(compliedPatternArray));
    return compliedPatternArray;
}

The compiled pattern array can be thought of as an array storing the pattern of characters in the pattern array. The main aim behind creating this array is to find the prefix and suffix in the pattern. If we know these elements in the pattern, we can avoid comparing from the start of the text and just compare the next character after the mismatch has occurred.
The compiled array stores the index position of previous occurrence of the current character in the pattern array.
Let's implement the algorithm itself:
public static List<Integer> performKMPSearch(String text, String pattern) {
    int[] compliedPatternArray = compilePatternArray(pattern);

    int textIndex = 0;
    int patternIndex = 0;

    List<Integer> foundIndexes = new ArrayList<>();

    while (textIndex < text.length()) {
        if (pattern.charAt(patternIndex) == text.charAt(textIndex)) {
            patternIndex++;
            textIndex++;
        }
        if (patternIndex == pattern.length()) {
            foundIndexes.add(textIndex - patternIndex);
            patternIndex = compliedPatternArray[patternIndex - 1];
        }

        else if (textIndex < text.length() && pattern.charAt(patternIndex) != text.charAt(textIndex)) {
            if (patternIndex != 0)
                patternIndex = compliedPatternArray[patternIndex - 1];
            else
                textIndex = textIndex + 1;
        }
    }
    return foundIndexes;
}

Here we start by comparing the characters in the pattern and text array sequentially. We keep moving forward until we keep getting a match of pattern and text arrays. This way, if we reach the end of the pattern array while matching it means we have found an occurrence of the pattern in the text.
However, if we find a mismatch when comparing the two arrays, we move the pattern character array index to the value in the compiledPatternArray() and also move to the next character in the text array. This is where the KMP search beats the brute-force approach, as it doesn't compare the text characters more than once if there is a mismatch.
Let's try running the algorithm:
String pattern = "AAABAAA";
String text = "ASBNSAAAAAABAAAAABAAAAAGAHUHDJKDDKSHAAJF";

List<Integer> foundIndexes = KnuthMorrisPrathPatternSearch.performKMPSearch(text, pattern);

if (foundIndexes.isEmpty()) {
    System.out.println("Pattern not found in the given text String");
} else {
    System.out.println("Pattern found in the given text String at positions: " + .stream().map(Object::toString).collect(Collectors.joining(", ")));
}

In the pattern text AAABAAA, the following pattern is observed and encoded in the pattern array:

The pattern A (Single A) is repeating in index 1 and again at 4.
The pattern AA (Double A) is repeating in index 2 and again at index 5.
The pattern AAA (3 A's) is repeating at index 6.

Let's see the output to validate our discussion so far:
Compiled Pattern Array [0, 1, 2, 0, 1, 2, 3]
Pattern found in the given text String at positions: 8, 14

The pattern we described is clearly shown to us in the compiled pattern array in the output.
With the help of this compiled array, the KMP search algorithm can search for the given pattern in the text without moving back in the text array.
Time Complexity
This algorithm needs to compare all the elements in the given text to find the pattern. The time required for that is O(N) . For compiling the pattern string we need to visit each of the character in the pattern and that is another O(M) iterations.
So the total time this algorithm takes will be O(M+N).
Space Complexity
We need O(M) space to store the compiled pattern for a given pattern of size M
Applications
This algorithm is particularly employed in text tools for finding patterns in text files.
Jump Search
Explanation
This search is similar to Binary Search but instead of jumping both forward and backward - we will only jump forward. Keep in mind that Jump Search also requires the collection to be sorted.
In Jump Search, we jump in the interval sqrt(arraylength) ahead until we reach an element greater than the current element or end of the array. On every jump, the previous step is recorded.
If we encounter an element greater than the element we are searching for, we stop jumping. Then, we run a Linear Search between the previous step and the current step.
This makes the search space a lot smaller for Linear Search, and thus it becomes a viable option.
Implementation
public static int jumpSearch(int[] integers, int elementToSearch) {

    int arrayLength = integers.length;
    int jumpStep = (int) Math.sqrt(integers.length);
    int previousStep = 0;

    while (integers[Math.min(jumpStep, arrayLength) - 1] < elementToSearch) {
        previousStep = jumpStep;
        jumpStep += (int)(Math.sqrt(arrayLength));
        if (previousStep >= arrayLength)
            return -1;
    }
    while (integers[previousStep] < elementToSearch) {
        previousStep++;
        if (previousStep == Math.min(jumpStep, arrayLength))
            return -1;
    }

    if (integers[previousStep] == elementToSearch)
        return previousStep;
    return -1;
}

We start with the jumpstep of size square-root of the length of the array and keep jumping forward with this same size until we find an element which is the same or greater than the element we are searching for.
So we first visit the element at integers[jumpStep], then integers[2jumpStep], integers[3jumpStep] and so on. We also store the previous element visited in the previousStep variable.
Once we find a value such that integers[previousStep] < elementToSearch < integers[jumpStep], we perform a linear search between integers[previousStep] and integers[jumpStep] or an element greater than elementToSearch.
We can use the algorithm like this:
int index = jumpSearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 67);
print(67, index);

Output:
67 found at Index 5

Time Complexity
Since we jump sqrt(arraylength) steps in each iteration, the time complexity for this search is O(sqrt(N)).
Space Complexity
The space complexity for this search is O(1) as it requires only one unit of space to store the element to be searched.
Application
This search is used over Binary Search when jumping back is costly. This constraint is faced when we use spinning medium like drives when seeking forward is easy but jumping in changed direction multiple times is costly.
Interpolation Search
Explanation
Interpolation Search is used to search elements in a sorted array. This search is particularly useful if we know the data in the underlying structure is uniformly distributed.
If the data is uniformly spread out, taking a guess about the location of an element can be more precise, opposed to Binary Search where we always try to find the element in the middle of the array.
Interpolation Search uses interpolation formulae to find the best probable place where the element can be found in the array. However, for this formulae to be effective the search array should be large otherwise it performs like Linear Search:
Implementation
public static int interpolationSearch(int[] integers, int elementToSearch) {

    int startIndex = 0;
    int lastIndex = (integers.length - 1);

    while ((startIndex <= lastIndex) && (elementToSearch >= integers[startIndex]) &&
           (elementToSearch <= integers[lastIndex])) {
        // using interpolation formulae to find the best probable position for this element to exist
        int pos = startIndex + (((lastIndex-startIndex) /
          (integers[lastIndex]-integers[startIndex]))*
                        (elementToSearch - integers[startIndex]));

        if (integers[pos] == elementToSearch)
            return pos;

        if (integers[pos] < elementToSearch)
            startIndex = pos + 1;

        else
            lastIndex = pos - 1;
    }
    return -1;
}

We can use this algorithm like this:
int index = interpolationSearch(new int[]{1,2,3,4,5,6,7,8}, 6);
print(67, index);

Output:
6 found at Index 5

Check out our hands-on, practical guide to learning Git, with best-practices, industry-accepted standards, and included cheat sheet. Stop Googling Git commands and actually learn it!Let's take a look at how the interpolation formulae works its magic to look for 6:
startIndex = 0
lastIndex = 7
integers[lastIndex] = 8
integers[startIndex] = 1
elementToSearch = 6

Now let's apply this values to the formulae to estimate the index of search Element:
$$
index = 0 + (7-0)/(8-1)*(6-1) = 5
$$
The element at integers[5] is 6 which is the element we were looking for. As we can see here, the index for the element is calculated in just one step since the data is uniformly spread.
Time Complexity
The best case time complexity for this algorithm is O(log log N) but in the worst case, i.e. when the elements are not uniformly distributed, it is comparable to linear search time complexity which is O(N).
Space Complexity
This algorithm also requires only one unit of space to store the element to be searched. Hence its space complexity is O(1).
Application
This search is useful when the data is uniformly distributed like Phone Numbers in a directory.
Exponential Search
Explanation
Exponential Search is used to search elements by jumping in exponential positions i.e. in powers of 2.
In this search we are basically trying to find a comparatively smaller range in which we can search the element using other bounded searches algorithms like Binary Search.
Needless to say, the collection should be sorted for this to work.
Implementation
public static int exponentialSearch(int[] integers, int elementToSearch) {

    if (integers[0] == elementToSearch)
        return 0;
    if (integers[integers.length - 1] == elementToSearch)
        return integers.length;

    int range = 1;

    while (range < integers.length && integers[range] <= elementToSearch) {
        range = range * 2;
    }

    return Arrays.binarySearch(integers, range / 2, Math.min(range, integers.length), elementToSearch);
}

We can use this algorithm like this:
int index = exponentialSearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 67);
print(67, index);

This is how the algorithm works:
We try to find an element which is greater than the element we are searching for. We do this to minimize the range of elements we are looking for. We increase the range by multiplying it with 2 and check again if we reached an element greater than the element we are searching for or the end of the array. Once either of this is achieved, we break out of the loop. Then we perform binary search with startIndex as range/2 and lastIndex as range.
In our case, this range value is achieved at 8 and the element at integers[8] is 95. So, the range where we perform binary search is:
startIndex = range/2 = 4

lastIndex = range = 8

With this the binary search call becomes:
Arrays.binarySearch(integers, 4, 8, 6);

Output:
67 found at Index 5

A important thing to note here we can speedup the multiplication by 2 by using the left shift operator range << 1instead of * operator.
Time Complexity
The worst-case time complexity for this type of search is O(log(N)).
Space Complexity
This algorithm requires O(1) space to store the element being searched if the underlying Binary Search algorithm is iterative.
If the underlying Binary Search algorithm is recursive, the space complexity becomes O(log(N)).
Applications
Exponential search is used when we have a huge or unbounded array. Applying Binary Search on the entire dataset may prove to be costly. Exponential Search can reduce this data into smaller, easily searchable partitions.
Fibonacci Search
Explanation
Fibonacci search employs divide and conquer approach wherein we unequally split elements as per the Fibonacci series. This search requires the array to be sorted.
Unlike in Binary Search where we divide the elements into equal halves to reduce the array range - In Fibonacci search we try to use addition or subtraction to get a smaller range.
Remember the formula for Fibonacci series is:
$$
Fibo(N) = Fibo(N-1)+Fibo(N-2)
$$
The first two numbers in this series are Fibo(0) = 0 and Fibo(1) = 1. So as per this formula, the series looks like this 0, 1, 1, 2, 3, 5, 8, 13, 21... Interesting observations to note here is that:
Fibo(N-2) is approximately 1/3rd of Fibo(N)
Fibo(N-1) is approximately 2/3rd of Fibo(N)
So when we use fibonacci series numbers to partition the range it gets split in the same ratio as above.
Implementation
Let's take a look at the implementation to get a clearer idea:
public static int fibonacciSearch(int[] integers, int elementToSearch) {

    int fibonacciMinus2 = 0;
    int fibonacciMinus1 = 1;
    int fibonacciNumber = fibonacciMinus2 + fibonacciMinus1;
    int arrayLength = integers.length;

    while (fibonacciNumber < arrayLength) {
        fibonacciMinus2 = fibonacciMinus1;
        fibonacciMinus1 = fibonacciNumber;
        fibonacciNumber = fibonacciMinus2 + fibonacciMinus1;
    }

    int offset = -1;

    while (fibonacciNumber > 1) {
        int i = Math.min(offset+fibonacciMinus2, arrayLength-1);

        if (integers[i] < elementToSearch) {
            fibonacciNumber = fibonacciMinus1;
            fibonacciMinus1 = fibonacciMinus2;
            fibonacciMinus2 = fibonacciNumber - fibonacciMinus1;
            offset = i;
        }

        else if (integers[i] > elementToSearch) {
            fibonacciNumber = fibonacciMinus2;
            fibonacciMinus1 = fibonacciMinus1 - fibonacciMinus2;
            fibonacciMinus2 = fibonacciNumber - fibonacciMinus1;
        }

        else return i;
    }

    if (fibonacciMinus1 == 1 && integers[offset+1] == elementToSearch)
        return offset+1;

    return -1;
}

We can run this algorithm like this:
int index = fibonacciSearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 67);
print(67, index);

This is how the algorithm works:
It starts by first finding the number in the Fibonacci series closest to but more than the length of array. This happens when fibonacciNumber is at 13 which is just more than array length - 10.
Next, we compare the elements of the array and on the basis of that comparison , we take one of the below actions:

Compare the element to be searched with the element at fibonacciMinus2 and return the index if the value matches.
If the elementToSearch is greater than the current element, we move one step back in the fibonacci series and change the values of fibonacciNumber, fibonacciMinus1 & fibonacciMinus2 accordingly. The offset is reset to the current Index.
If the elementToSearch is smaller than the current element, we move two steps back in the fibonacci series and change the values of fibonacciNumber, fibonacciMinus1 & fibonacciMinus2 accordingly.

Output:
67 found at Index 5

Time Complexity
The worst-case time complexity for this search is O(log(N)).
Space Complexity
While we need to save the three numbers in Fibonacci series and the element to be searched we need four extra units of space.
This requirement of space does not increase with the size of the input array. Hence, we can say that the space complexity for Fibonacci search is O(1).
Applications
This search is used when the division is a costly operation for the CPU to perform. Algorithms like Binary Search tend to fare poorly as they use division to divide the array.
Another benefit of this search is when elements of the input array cannot fit into the RAM. In such situations, a localized scope of operation that this algorithm performs helps it to run much faster.
Java Collections API
Now that we have seen the implementation of multiple algorithms in Java, let's also take a brief look at the way searching is performed in different Java Collections.
Arrays
Arrays in Java can be searched using one of the java.util.BinarySearch methods. The binary Search in the Open JDK version uses the iterative form of the search.
Let's take a quick look at how we can use this method:
int[] integers = {3, 22, 27, 47, 57, 67, 89, 91, 95, 99};

int elementToSearch = 67;

int index = java.util.Arrays.binarySearch(integers, elementToSearch);

Output:
67 found at Index 5

The List Interface
The List Interface has primarily two methods which can be used for searching: indexOf() and contains().
The indexOf() method returns the index of the element if it exists in the list or -1 if it doesn't exist.
The contains() method returns true or false depending upon the existence of the element. It internally calls the indexOf() method.
The List interface uses Sequential Search to perform the index lookup and hence its time complexity is O(N).
Let's try out a search operation on a List:
java.util.List<Integer> integers = new java.util.ArrayList<>();
integers.add(3);
integers.add(22);
integers.add(27);
integers.add(47);
integers.add(57);
integers.add(67);
integers.add(89);
integers.add(91);
integers.add(95);
integers.add(99);

int elementToSearch = 67;

int index = integers.indexOf(elementToSearch);

Output:
67 found at Index 5

Similarly, if we are not interested in the index but only want to know if the element exists in the List or not we can use the contains() method:
integers.contains(67)

Output:
true

The Map Interface
The Map is a key-value pair data structure. The Map interface in Java uses HashBased searching as well as the Binary Search Tree.
The java.util.HashMap class uses a hash-value of the key to store the elements in the Map. Retrieving the element from the Map using right keys to hash and a good Hashing algorithm (such that no collisions occur) is O(1).
Another implementation of the Map interface is the java.util.TreeMap, which internally uses Red-Black Tree which is a type of self-balancing binary search tree. The elements added to this tree are automatically stored in the sorted fashion by the tree.
The time complexity of searching a Binary Tree is O(log(N)).
Let's see how we can search an element in a Map:
java.util.Map<Integer, String> integers = new java.util.HashMap<>();
integers.put(3,"three");
integers.put(22,"twentytwo");
integers.put(27,"twentyseven");
integers.put(47,"fortyseven");
integers.put(57,"fiftyseven");
integers.put(67,"sixtyseven");
integers.put(89,"eightynine");
integers.put(91,"ninetyone");
integers.put(95,"ninetyfive");
integers.put(99,"ninetynine");

String value = integers.get(67);

System.out.println("the value at key 67 is: " + value);

We have created a map with a key as an Integer and the value as that Integer in words. We then search for a key and get the Integer as words in the output.
An important thing to note here is that the map will not store duplicate keys. If we try to insert a duplicate value it will overwrite the existing key and value with the new one.
Output:
the value at key 67 is: sixtyseven

Map interface also contains the containsKey() method which can be used to determine if a given key exists or not:
integers.containsKey(67);

The Set Interface
The Set data-structure is used to store unique elements. The Set interface is essentially a wrapper over the Map interface described above storing elements in the Key of the Map.
As with the Map interface it uses the Binary and Hash-based search.
java.util.Set<Integer> integers = new java.util.HashSet<>();
integers.add(3);
integers.add(22);
integers.add(27);
integers.add(47);
integers.add(57);
integers.add(67);
integers.add(89);
integers.add(91);
integers.add(95);
integers.add(99);

int elementToSearch = 67;

boolean isNumberExists = integers.contains(elementToSearch);

if (isNumberExists)
    System.out.println(elementToSearch + " exists in the set");
else
    System.out.println(elementToSearch + " does not exist in the set");

There is no index in the Set interface and as such the search operation contains() returns true or false depending upon the existence of the element being searched.
In this case, since the element exists in the set we get the below output:
67 exists in the set

Search Algorithm Time Comparison
That being said, it's often useful to run all of these algorithms a few times to get an idea of how they perform.
Let's search for the element 573400 in a sorted array that's populated with a million integers.
Here are the results of the algorithms:

  
    time(ns)
    Linear
    Binary (Iterative)
    Binary (Recursive)
    Jump
    Interpolation
    Exponential
    Fibonacci
  
  
    First Run
    5 229 901
    23 014
    14 928
    125 647
    18 661
    49 762
    13 373
  
  
    Second Run
    8 436 389
    24 570
    14 306
    329 046
    18 349
    206 820
    21 770
  
  
    Third Run
    7 207 909
    24 569
    23 326
    585 005
    19 593
    106 054
    23 325
  
  
    Fourth Run
    5 888 615
    33 589
    27 057
    218 327
    23 015
    111 341
    25 813
  
  
    Fifth Run
    3 002 466
    20 216
    46 962
    132 800
    15 861
    65 311
    20 216
  
  
    Sixth Run
    6 896 901
    12 440
    26 124
    212 107
    7 465
    106 054
    38 254
  
  
    Seventh Run
    6 916 495
    59 714
    13 373
    210 241
    15 240
    126 891
    13 684
  
  
    Eight Run
    6 781 828
    22 393
    46 962
    159 235
    10 575
    83 972
    26 436
  
  
    Ninth Run
    6 917 116
    11 507
    18 660
    265 911
    28 302
    130 002
    12 751
  
  
    Tenth Run
    3 811 085
    41 053
    89 259
    302 922
    26 436
    183 184
    25 192
  

It's easy to see that Linear Search takes significantly longer than any other algorithm to search for this element, since it evaluated each and every element before the one we're searching for. If we were searching for the first element, Linear Search would be the most efficient one here.
It's also easy to see the Binary, Interpolation and Fibonacci Search show the best results for this particular array.
Conclusion
Every system has its own unique set of constraints and requirements. A correctly used search algorithm, based on those constraints, can go a long way in determining the performance of the system.
In this article, we took a look at how the different search algorithms work and under what circumstances they are a perfect fit. We also had a look at how Java uses different search algorithms in its built-in Collections API.
As always, you can find the source code of the algorithms described in this article here.
