Searching Algorithms:
A basic, fundamental computing process that locates a specific piece of data among a group of data is termed a search algorithm (Casey).
The search algorithms are divided into two categories according to their search operation. 1) Sequential Search and, 2) Interval Search.
According to (Searching Algorithms – GeeksforGeeks) there are 11 types of searching algorithms present in data structures and algorithms. They are given below. (Searching Algorithms – GeeksforGeeks)
- Linear Search
- Binary Search
- Jump Search
- Interpolation Search
- Exponential Search
- Sublist Search (Search a linked list in another list)
- Fibonacci Search
- The Ubiquitous Binary Search
- Recursive program to linearly search an element in a given array
- Recursive function to do a substring search
- Unbounded Binary Search
- Linear Search (Code):
Code Source (Searching Algorithms – GeeksforGeeks)
// Java code for linearly searching x in arr[]. If x
// is present then return its location, otherwise
// return -1
class GFG
{
public static int search(int arr[], int x)
{
int n = arr.length;
for (int i = 0; i < n; i++)
{
if (arr[i] == x)
return i;
}
return -1;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
// Function call
int result = search(arr, x);
if (result == -1)
System.out.print(
"Element is not present in array");
else
System.out.print("Element is present at index "
+ result);
}
}
Binary Search (Code):
A Binary Search algorithm can be implemented in two ways, recursive or iterative. The implementation of both these methods is given below.
Code Source (Searching Algorithms – GeeksforGeeks)
- Recursive Approach
// 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);
}
}
Iterative Approach
// Java implementation of iterative Binary Search
class BinarySearch {
// Returns index of x if it is present in arr[],
// else return -1
int binarySearch(int arr[], int x)
{
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
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, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at "
+ "index " + result);
}
}
Jump Search (Code):
Code Source (Searching Algorithms – GeeksforGeeks)
// 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);
}
}
Interpolation Search (Code):
Code Source (Searching Algorithms – GeeksforGeeks)
// Java program to implement interpolation
// search with recursion
import java.util.*;
class GFG {
// If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
public static int interpolationSearch(int arr[], int lo,
int hi, int x)
{
int pos;
// Since array is sorted, an element
// present in array must be in range
// defined by corner
if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
// Probing the position with keeping
// uniform distribution in mind.
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 right sub array
if (arr[pos] < x)
return interpolationSearch(arr, pos + 1, hi,
x);
// If x is smaller, x is in left sub array
if (arr[pos] > x)
return interpolationSearch(arr, lo, pos - 1,
x);
}
return -1;
}
// Driver Code
public static void main(String[] args)
{
// Array of items on which search will
// be conducted.
int arr[] = { 10, 12, 13, 16, 18, 19, 20, 21,
22, 23, 24, 33, 35, 42, 47 };
int n = arr.length;
// Element to be searched
int x = 18;
int index = interpolationSearch(arr, 0, n - 1, x);
// If element was found
if (index != -1)
System.out.println("Element found at index "
+ index);
else
System.out.println("Element not found.");
}
}
Exponential Search (Code):
Code Source (Searching Algorithms – GeeksforGeeks)
// Java program to
// find an element x in a
// sorted array using
// Exponential search.
import java.util.Arrays;
class GFG
{
// Returns position of
// first occurrence of
// x in array
static int exponentialSearch(int arr[],
int n, int x)
{
// If x is present at first 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-1), x);
}
// Driver code
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);
}
}
Sublist Search (Code):
Code Source (Searching Algorithms – GeeksforGeeks)
// Java program to find a list in second list
import java.util.*;
class GFG
{
// A Linked List node
static class Node
{
int data;
Node next;
};
// Returns true if first list is
// present in second list
static boolean findList(Node first,
Node second)
{
Node ptr1 = first, ptr2 = second;
// If both linked lists are empty,
// return true
if (first == null && second == null)
return true;
// Else If one is empty and
// other is not, return false
if (first == null ||
(first != null && second == null))
return false;
// Traverse the second list by
// picking nodes one by one
while (second != null)
{
// Initialize ptr2 with
// current node of second
ptr2 = second;
// Start matching first list
// with second list
while (ptr1 != null)
{
// If second list becomes empty and
// first not then return false
if (ptr2 == null)
return false;
// If data part is same, go to next
// of both lists
else if (ptr1.data == ptr2.data)
{
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
// If not equal then break the loop
else break;
}
// Return true if first list gets traversed
// completely that means it is matched.
if (ptr1 == null)
return true;
// Initialize ptr1 with first again
ptr1 = first;
// And go to next node of second list
second = second.next;
}
return false;
}
/* Function to print nodes in a given linked list */
static void printList(Node node)
{
while (node != null)
{
System.out.printf("%d ", node.data);
node = node.next;
}
}
// Function to add new node to linked lists
static Node newNode(int key)
{
Node temp = new Node();
temp.data= key;
temp.next = null;
return temp;
}
// Driver Code
public static void main(String[] args)
{
/* Let us create two linked lists to test
the above functions. Created lists shall be
a: 1->2->3->4
b: 1->2->1->2->3->4*/
Node a = newNode(1);
a.next = newNode(2);
a.next.next = newNode(3);
a.next.next.next = newNode(4);
Node b = newNode(1);
b.next = newNode(2);
b.next.next = newNode(1);
b.next.next.next = newNode(2);
b.next.next.next.next = newNode(3);
b.next.next.next.next.next = newNode(4);
if(findList(a, b) == true)
System.out.println("LIST FOUND");
else
System.out.println("LIST NOT FOUND");
}
}
Fibonacci Search (Code):
Code Source (Searching Algorithms – GeeksforGeeks)
// Java program for Fibonacci Search
import java.util.*;
class Fibonacci {
// Utility function to find minimum
// of two elements
public static int min(int x, int y)
{
return (x <= y) ? x : y;
}
/* Returns index of x if present, else returns -1 */
public static int fibMonaccianSearch(int arr[], int x,
int n)
{
/* Initialize fibonacci numbers */
int fibMMm2 = 0; // (m-2)'th Fibonacci No.
int fibMMm1 = 1; // (m-1)'th Fibonacci No.
int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci
/* fibM is going to store the smallest
Fibonacci Number greater than or equal to n */
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
// Marks the eliminated range from front
int offset = -1;
/* while there are elements to be inspected.
Note that we compare arr[fibMm2] with x.
When fibM becomes 1, fibMm2 becomes 0 */
while (fibM > 1) {
// Check if fibMm2 is a valid location
int i = min(offset + fibMMm2, n - 1);
/* If x is greater than the value at
index fibMm2, cut the subarray array
from offset to i */
if (arr[i] < x) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
}
/* If x is less than the value at index
fibMm2, cut the subarray after i+1 */
else if (arr[i] > x) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
}
/* element found. return index */
else
return i;
}
/* comparing the last element with x */
if (fibMMm1 == 1 && arr[n-1] == x)
return n-1;
/*element not found. return -1 */
return -1;
}
// driver code
public static void main(String[] args)
{
int arr[] = { 10, 22, 35, 40, 45, 50,
80, 82, 85, 90, 100,235};
int n = 12;
int x = 235;
int ind = fibMonaccianSearch(arr, x, n);
if(ind>=0)
System.out.print("Found at index: "
+ind);
else
System.out.print(x+" isn't present in the array");
}
}
The Ubiquitous Binary Search (Code):
Code Source (Searching Algorithms – GeeksforGeeks)
// Java code to implement the Ubiquitous Binary Search
import java.util.*;
class GFG {
// Returns location of key, or -1 if not found
static int BinarySearch(int A[], int l, int r, int key)
{
int m;
while( l < r )
{
m = l + (r-l)/2;
if( A[m] == key ) // first comparison
return m;
if( A[m] < key ) // second comparison
l = m + 1;
else
r = m - 1;
}
return -1;
}
}
Recursive program to linearly search an element in a given array (Code):
Code Source (Searching Algorithms – GeeksforGeeks)
// Recursive Java program to search x in array
class Test
{
static int arr[] = {12, 34, 54, 2, 3};
/* Recursive Method to search x in arr[l..r] */
static int recSearch(int arr[], int l, int r, int x)
{
if (r < l)
return -1;
if (arr[l] == x)
return l;
if (arr[r] == x)
return r;
return recSearch(arr, l+1, r-1, x);
}
// Driver method
public static void main(String[] args)
{
int x = 3;
//Method call to find x
int index = recSearch(arr, 0, arr.length-1, x);
if (index != -1)
System.out.println("Element " + x + " is present at index " +
index);
else
System.out.println("Element " + x + " is not present");
}
}
Recursive function to do a substring search (Code):
Code Source (Searching Algorithms – GeeksforGeeks)
// Recursive Java program to find if a given pattern is
// present in a text
class GFG {
static int exactMatch(String text, String pat, int text_index, int pat_index) {
if (text_index == text.length() && pat_index != pat.length())
return 0;
// Else If last character of pattern reaches
if (pat_index == pat.length())
return 1;
if (text.charAt(text_index) == pat.charAt(pat_index))
return exactMatch(text, pat, text_index + 1, pat_index + 1);
return 0;
}
// This function returns true if 'text' contain 'pat'
static int contains(String text, String pat, int text_index, int pat_index) {
// If last character of text reaches
if (text_index == text.length())
return 0;
// If current characters of pat and text match
if (text.charAt(text_index) == pat.charAt(pat_index)) {
if (exactMatch(text, pat, text_index, pat_index) == 1)
return 1;
else
return contains(text, pat, text_index + 1, pat_index);
}
// If current characters of pat and tex don't match
return contains(text, pat, text_index + 1, pat_index);
}
// Driver program to test the above function
public static void main(String args[]) {
System.out.println(contains("geeksforgeeks", "geeks", 0, 0));
System.out.println(contains("geeksforgeeks", "geeksquiz", 0, 0));
System.out.println(contains("geeksquizgeeks", "quiz", 0, 0));
}
}
Unbounded Binary Search (Code):
Code Source (Searching Algorithms – GeeksforGeeks)
// Java program for Unbounded Binary Search
import java.util.*;
class Binary
{
public static int f(int x)
{ return (x*x - 10*x - 20); }
// Returns the value x where above
// function f() becomes positive
// first time.
public static int findFirstPositive()
{
// When first value itself is positive
if (f(0) > 0)
return 0;
// Find 'high' for binary search
// by repeated doubling
int i = 1;
while (f(i) <= 0)
i = i * 2;
// Call binary search
return binarySearch(i / 2, i);
}
// Searches first positive value of
// f(i) where low <= i <= high
public static int binarySearch(int low, int high)
{
if (high >= low)
{
/* mid = (low + high)/2 */
int mid = low + (high - low)/2;
// If f(mid) is greater than 0 and
// one of the following two
// conditions is true:
// a) mid is equal to low
// b) f(mid-1) is negative
if (f(mid) > 0 && (mid == low || f(mid-1) <= 0))
return mid;
// If f(mid) is smaller than or equal to 0
if (f(mid) <= 0)
return binarySearch((mid + 1), high);
else // f(mid) > 0
return binarySearch(low, (mid -1));
}
/* Return -1 if there is no positive
value in given range */
return -1;
}
// driver code
public static void main(String[] args)
{
System.out.print ("The value n where f() "+
"becomes positive first is "+
findFirstPositive());
}
}
References:
Casey, Kela. “Let Us Understand Searching Algorithms.” CODERSERA, 5 Aug. 2020, https://codersera.com/blog/let-us-understand-searching-algorithms/.
Searching Algorithms – GeeksforGeeks. https://www.geeksforgeeks.org/searching-algorithms/. Accessed 14 Aug. 2022.
“Sorting Algorithms.” GeeksforGeeks, https://www.geeksforgeeks.org/sorting-algorithms/. Accessed 14 Aug. 2022.
“Sorting Algorithms Explained with Examples in JavaScript, Python, Java, and C++.” FreeCodeCamp.Org, 4 Dec. 2019, https://www.freecodecamp.org/news/sorting-algorithms-explained-with-examples-in-python-java-and-c/.