In the world of Java Implementation of All Searching Algorithms, the comprehensive guidance provided by programming assignments help empowers students to delve into the intricacies of various search techniques, allowing them to gain hands-on experience and insight into the efficiency and applicability of each algorithm in different scenarios.
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/.