Searching Algorithms in Java

In this article, we will discuss different searching algorithms and it's implementation using the Java Programming Language.

Let's get started with what is searching for ? and why do we need searching ?.

What is Searching?

In computer science, searching is the process of finding an item with specified properties from a collection of items. The items may be stored as records in a database, simple data elements in arrays, text in files, nodes in trees, vertices and edges in graphs, or they may be elements of other search spaces.

Why do we need Searching?

Searching is one of the core computer science algorithms. We know that today’s computers store a lot of information. To retrieve this information proficiently we need very efficient searching algorithms.

There are certain ways of organizing the data that improves the searching process. That means, if we keep the data in proper order, it is easy to search the required element. Sorting is one of the techniques for making the elements ordered. In this article, we will see different searching algorithms.

In this article, we will discuss three searching algorithms and it's implementation using the Java Programming language.

Searching Algorithms

1. Linear Search Algorithm
2. Binary Search Algorithm
3. Interpolation Search Algorithm

1. Linear Search Algorithm

In computer science, linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.

Let's demonstrate the implementation of a linear search algorithm using Java.

/**
 * In computer science, linear search or sequential search is a method for 
 * finding a target value within a list. It sequentially checks each element of 
 * the list for the target value until a match is 
 * found or until all the elements have been searched.
 * <p>
 * Worst-case performance      O(n)<br>
 * Best-case performance       O(1)<br>
 * Average performance         O(n)<br>
 * Worst-case space complexity O(1)<br>
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/Linear_search">Linear Search (Wikipedia)</a>
 * <br>
 * @author Ramesh Fadatare
 */
public class LinearSearch {

    public static final int unorderedLinearSearch(int value, int[] array) {
        for (int i = 0; i < array.length; i++) {
            int iValue = array[i];
            if (value == iValue)
                return i;
        }
        return Integer.MAX_VALUE;
    }
    
    public static final int orderedLinearSearch(int value, int[] array) {
        for (int i = 0; i < array.length; i++) {
            if (value == array[i]){
                return i;
            }
            else if (array[i] > value){
             return -1;
            }
        }
        return Integer.MAX_VALUE;
    }
    
    public static void main(String[] args) {
      int[] integers = {1,2,3,4,5,6,7,8,8,8,9,9,9,0};
         //the element that should be found
         int shouldBeFound = 9;

         int atIndex = LinearSearch.unorderedLinearSearch(shouldBeFound, integers);

         System.out.println(String.format("Should be found: %d. Found %d at index %d. An array length %d"
                 , shouldBeFound, integers[atIndex], atIndex, integers.length));
         
         int[] sortedArray = {10,20,30,40,50};
         //the element that should be found
         int key = 30;
         
         atIndex = LinearSearch.orderedLinearSearch(key, sortedArray);

         System.out.println(String.format("Should be found: %d. Found %d at index %d. An array length %d"
                 , key, sortedArray[atIndex], atIndex, sortedArray.length));
         
 }
}

Output:

Should be found: 9. Found 9 at index 10. An array length 14
Should be found: 30. Found 30 at index 2. An array length 5

Read more about linear search algorithms on Linear Search Algorithm in Java

2. Binary Search Algorithm

Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.

Binary Search Implementation using Java

Let's write a source code for binary search in Java. There are many ways we can write logic for binary search:

1. Iterative implementation
2. Recursive Implementation
3. Using Arrays.binarySearch()
4. Using Collections.binarySearch()

Iterative Implementation

public class BinarySearch {

 public int binarySearchIteratively(int[] sortedArray, int key) {
  int low = 0;
     int high = sortedArray.length - 1;
  int index = Integer.MAX_VALUE;

  while (low <= high) {

   int mid = (low + high) / 2;

   if (sortedArray[mid] < key) {
    low = mid + 1;
   } else if (sortedArray[mid] > key) {
    high = mid - 1;
   } else if (sortedArray[mid] == key) {
    index = mid;
    break;
   }
  }
  return index;
 }

 
 public static void main(String[] args) {
  int[] sortedArray = { 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 };
     int key = 6;
     
     BinarySearch binSearch = new BinarySearch();
        int index = binSearch.binarySearchIteratively(sortedArray, key);
        System.out.println("Search element found " + key+ " in location index : " + index);
 }
}

Output:

Search element  6 found in location index : 7

The binarySearchIteratively method takes a sortedArray, key & the low & high indexes of the sortedArray as arguments. When the method runs for the first time the low, the first index of the sortedArray, is 0, while the high, the last index of the sortedArray, is equal to its length – 1.

The middle is the middle index of the sortedArray. Now the algorithm runs a while loop comparing the key with the array value of the middle index of the sortedArray.

Recursive Implementation

Now, let’s have a look at a simple, recursive implementation as well:

public class BinarySearch {

 public int binarySearchRecursively(int[] sortedArray, int key, int low, int high) {

  int middle = (low + high) / 2;
  if (high < low) {
   return -1;
  }

  if (key == sortedArray[middle]) {
   return middle;
  } else if (key < sortedArray[middle]) {
   return binarySearchRecursively(sortedArray, key, low, middle - 1);
  } else {
   return binarySearchRecursively(sortedArray, key, middle + 1, high);
  }
 }

 
 public static void main(String[] args) {
  int[] sortedArray = { 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 };
     int key = 6;
     
     BinarySearch binSearch = new BinarySearch();
        
        int index = binSearch.binarySearchRecursively(sortedArray, key, 0, sortedArray.length -1);
        System.out.println("Search element found in location index : " + index);
        
 }
}

Output:

Search element found in location index : 7

The binarySearchRecursively method accepts a sortedArray, key, the low and high indexes of the sortedArray.

Using Arrays.binarySearch()

public class BinarySearch {

 public int runBinarySearchUsingJavaArrays(int[] sortedArray, Integer key) {
  int index = Arrays.binarySearch(sortedArray, key);
  return index;
 }

 public static void main(String[] args) {
  int[] sortedArray = { 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 };
     int key = 6;
     
     BinarySearch binSearch = new BinarySearch();
        int index1 = binSearch.runBinarySearchUsingJavaArrays(sortedArray, key);
        System.out.println("Search element found in location index : " + index1);
 }
}

Output:

Search element found in location index : 7

Using Collections.binarySearch()

public class BinarySearch {

 public int runBinarySearchUsingJavaCollections(List<Integer> sortedList, Integer key) {
  int index = Collections.binarySearch(sortedList, key);
  return index;
 }
 
 public static void main(String[] args) {
  Integer[] sortedArray = { 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 };
     int key = 6;
     
     BinarySearch binarySearch = new BinarySearch();
        int index1 = binarySearch.runBinarySearchUsingJavaCollections(Arrays.asList(sortedArray), key);
        System.out.println("Search element found in location index : " + index1);
 }
}

Output:

Search element found in location index : 7

Time Complexity: The time complexity of Binary Search can be written as

T(n) = T(n/2) + c 

Auxiliary Space: O(1) in the case of iterative implementation. In case of recursive implementation, O(Logn) recursion call stack space.

Algorithmic Paradigm: Decrease and Conquer.

Read more about binary search algorithms on Binary Search Algorithm in Java

3. Interpolation Search Algorithm

Interpolation search is an algorithm for searching for a given key in an indexed array that has been ordered by numerical values assigned to the keys (key values). It parallels how humans search through a telephone book for a particular name, the key value by which the book's entries are ordered.

Interpolation Search Implementation in Java

/**
 * Interpolation search is an algorithm for searching for a given key in an indexed array.
 * @author Ramesh Fadatare
 */
public class InterpolationSearch {

    private static int[] sorted = null;

    // Assuming the array is sorted
    public static final int find(int value, int[] array) {
        InterpolationSearch.sorted = array;
        try {
            return recursiveFind(value, 0, InterpolationSearch.sorted.length - 1);
        } finally {
            InterpolationSearch.sorted = null;
        }
    }

    private static int recursiveFind(int value, int start, int end) {
        if (start == end) {
            int lastValue = sorted[start]; // start==end
            if (value == lastValue)
                return start; // start==end
            return Integer.MAX_VALUE;
        }

        final int mid = start + ((value - sorted[start]) * (end - start)) / (sorted[end] - sorted[start]);
        if (mid < 0 || mid > end)
            return Integer.MAX_VALUE;
        int midValue = sorted[mid];
        if (value == midValue)
            return mid;
        if (value > midValue)
            return recursiveFind(value, mid + 1, end);
        return recursiveFind(value, start, mid - 1);
    }
    
    public static void main(String[] args) {
      int[] integers = {10,20,30,40,50,60,70,80,90,100};

         //the element that should be found
         int key = 100;

         InterpolationSearch search = new InterpolationSearch();
         int atIndex = search.find(key, integers);
         
         System.out.println("Remember array index starts from 0");
         System.out.println("The size of the array is : " + integers.length);
         System.out.println("The element found at index : " + atIndex);
 }
}

Output:

Remember array index starts from 0
The size of the array is : 10
The element found at index : 9

Read more about Interpolation search algorithms on Interpolation Search Algorithm

Master in Data Structures and Algorithms in Java

Learn Complete Java Programming on Java Tutorial | Learn Java Programming with Examples