Categories
Samples

Assignment Example of Java Implementation of All Searching Algorithms

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

  1. Linear Search
  2. Binary Search
  3. Jump Search
  4. Interpolation Search
  5. Exponential Search
  6. Sublist Search (Search a linked list in another list)
  7. Fibonacci Search
  8. The Ubiquitous Binary Search
  9. Recursive program to linearly search an element in a given array
  10. Recursive function to do a substring search
  11. Unbounded Binary Search
  1. 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/.