What exactly is searching?
Searching is discovering an item with specific qualities from a collection of items in computer science. Items can be kept in a database as records, as simple data pieces in arrays, as text in files, as nodes in trees, as vertices and edges in graphs, or as parts of different search spaces.
Why do we require Searching Algorithms?
Searching is a fundamental algorithm in computer science. We all know that today's computers can hold a lot of data. We need very efficient searching methods to obtain this information effectively.
Specific approaches to data organization help the search process. If we preserve the data in the appropriate sequence, we can easily find the desired piece. Sorting is one way of organizing the elements. In this essay, we will look at various search algorithms.
In this post, we will look at three different searching algorithms and how they are implemented in Java.
Searching Algorithms in Java
Below is a list of Java searching algorithms that we will look at.
Linear Search Algorithm
Binary Search Algorithm
Interpolation Search Algorithm
Linear Search Algorithm in Java
In Java, linear search algorithm or sequential search, is a method for locating a certain value inside a list. It checks each element of the list for the target value until a match is found or all of the elements have been searched.
Let's look at how to create a linear search algorithm in Java.
Example:
import java.util.*;
public class LinearSearch {
public static void main(String args[]) {
// taking user input
Scanner sc = new Scanner(System.in);
System.out.println("Enter number of elements:");
int N = sc.nextInt();
System.out.println("Enter elements:");
// storing elements in an array
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = sc.nextInt();
}
// asking the user for the target element
System.out.println("Enter target element:");
int target = sc.nextInt();
// using linear search to find an element
int index = Search(N, arr, target);
// printing result
System.out.println("The array is as follows:\n" + Arrays.toString(arr));
if (index == -1) System.out.println(
"Sorry, element not found"
); else System.out.println("The element is present at index " + index);
}
public static int Search(int N, int[] arr, int target) {
// using for loop to traverse the array
for (int i = 0; i < N; i++) {
//If the target is found, return
if (arr[i] == target) return i + 1;
}
//If the target is not present return
return -1;
}
}
Output:
Enter elements:
10
9
8
7
6
Enter target element:
7
The array is as follows:
[10, 9, 8, 7, 6]
The element is present at index 4
Benefits of Linear Search
Linear search is straightforward to implement and comprehend.
The linear search can be used whether the array is ordered or not. It applies to arrays of any data type.
There is no need for more RAM.
It is a good algorithm for tiny datasets.
Drawbacks of Linear Search
Linear Search has the following disadvantages:
Linear search has an O(n) time complexity, slowing large datasets.
Large arrays are not recommended.
Linear search techniques, such as hash tables, can be less efficient.
Linear Search Enhancement
As previously stated, the time required to search an element using linear search is linear. This is one disadvantage of utilizing linear search for large data sets. It has been noted that the chance of searching for the same key element repeatedly exists when looking for a key element. Using this discovery, we can improve the performance of a linear search.
The goal is for the process to take less time if the same element is searched again. As a result, in this scenario, Linear Search can be enhanced by employing the following two techniques:
Move to the Front
Transportation
Binary Search Algorithm in Java
In Java, binary search is a search algorithm that locates the position of a target value within a sorted array. The binary search compares the target value to the array's middle element. It only works with a sorted set of components. To utilize binary search on a collection, first sort the collection.
When performing actions on a sorted set using the binary search, the number of iterations can always be lowered based on the searched value. The accompanying screenshot shows how to discover the mid-element. The analogy of binary search is to leverage the array's sorted information to lower the time complexity to O(log n).
Understanding the Binary Search Algorithm
Let's look at the pseudo-code below to get a better sense of it.
Procedure binary_search
A ← sorted array
n ← size of an array
x ← value to be searched
Set low = 1
Set high = n
while x not found
if high < low
EXIT: x does not exist.
set mid = low + ( high - low ) / 2
if A[mid] < x set low = mid + 1 if A[mid]> x
set high = mid - 1
if A[mid] = x
EXIT: x found at location mid
end while
end procedure
Explanation:
Step 1: Compare x to the center element.
Step 2: If x corresponds to the middle element, you must return the mid index.
Step 3: If not, If x is greater than the mid element, it can only be found after the mid element on the right side half array. As a result, you repeat the right half.
Step 4: Otherwise, if (x is less than), repeat for the left half.
Example 1: 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
Example 2: Recursive Implementation
public class BinarySearch {
// Java implementation of recursive Binary Search
// Returns index of x if it is present in arr[l..h], else return -1
int binarySearch(int a[], int l, int h, int x)
{
if (h >= l) {
int mid = l + (h - l) / 2;
// If the element is present in the middle itself
if (a[mid] == x)
return mid;
// If the element is smaller than mid, then it can only be present in the left subarray
if (a[mid] >x)
return binarySearch(arr, l, mid - 1, x);
// Else, the element can only be present in the right subarray
return binarySearch(arr, mid + 1, h, x);
}
// We reach here when an element is not present in the array
return -1;
}
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int a[] = { 20, 30, 40, 10, 50 };
int n = a.length;
int x = 40;
int res = ob.binarySearch(a, 0, n - 1, x);
if (res == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index " + res);
}
}
Output:
Element found at index 2
Example 3: Using Arrays.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
Benefits of Binary Search
For large arrays, binary search is faster than linear search. The time it takes to execute a linear search increase linearly as the size of the array grows, whereas the time it takes to perform a binary search increase logarithmically.
Binary search is more efficient than other time-consuming searching methods, such as interpolation search or exponential search.
Binary search is straightforward to implement and understand, making it an excellent choice for various applications.
Binary search is ideal for scanning big datasets stored in external memory, such as a hard drive or the cloud.
Binary search can be a foundation for more advanced algorithms in computer graphics and machine learning.
Cons of Binary Search
We demand that the array be sorted. If the array still needs to be sorted, we must sort it before we can search it. This adds O(N * logN) time complexity to the sorting phase, rendering binary search obsolete.
Binary search necessitates storing the data structure under consideration in contiguous memory regions. This can be an issue if the data structure is too vast to fit in memory or is saved on external memory, such as a hard drive or the cloud.
Binary search requires that the array elements be similar, meaning they can be ordered. This can be an issue if the array's items are not naturally sorted or the ordering needs to be better-defined.
When exploring massive datasets that do not fit in memory, the binary search may be less efficient than other techniques, such as hash tables.
Interpolation search in Java
Interpolation search is an algorithm for finding a given key in an indexed array sorted by the numerical values assigned to the keys (key values). It is analogous to how individuals look through a phone book for a specific name, which is the key value of organizing the book's entries.
Example
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 = {1,2,3,4,5,6,7,8,9,10};
//the element that should be found
int key = 100;
InterpolationSearch search = new InterpolationSearch();
int atIndex = search.find(key, integers);
System.out.println("Always 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:
Always remember array index starts from 0
The size of the array is: 10
The element found at index: 2147483647
In Java, interpolation search is a search algorithm used to locate a target value within a sorted array or list. While interpolation search has some advantages in terms of time complexity, it also has significant downsides compared to other search algorithms in some instances. The followings are the benefits and drawbacks of interpolation search in Java:
Advantages
Faster on evenly distributed data: When the data is uniformly distributed, interpolation search can be faster than other search methods, such as binary. This is because, compared to binary search, interpolation search uses an interpolation algorithm to estimate the position of the target value, which might result in faster convergence toward the target value.
Interpolation search is handy for exploring big sorted datasets because it can converge toward the target value faster than binary search in some instances. This can result in faster searching for values in massive arrays or lists.
Disadvantages
Interpolation search requires sorted data: For reliable results, the data must be sorted in ascending or descending order. Interpolation search may only discover the correct position of the target value if the data is sorted, resulting in accurate results.
Interpolation search is limited to numerical data since it relies on numerical values and their ordering to approximate the position of the target value. Unless a custom interpolation function is created, it may not be acceptable for non-numerical data types or bespoke objects that do not have a natural ordering.
Interpolation search is not always quicker than binary search: While it is faster than binary search on uniformly distributed data, it is only sometimes faster in all cases. A binary search may be more efficient in some instances, such as when the data is not uniformly distributed or when the array or list is short.
In worst-case conditions, performance may suffer: In worst-case situations, such as when the data is unevenly distributed or contains repeated values, the performance of the interpolation search can suffer dramatically. Interpolation search may not provide significant performance gains over other search algorithms in such instances and may even perform poorly.
Finally, interpolation search in Java provides advantages in terms of possible speed on uniformly distributed data and adaptability for huge datasets. However, it has drawbacks, including its dependency on sorted data, restricted applicability to numerical data, and the potential for poor performance in some cases.
When determining whether to use interpolation search or alternative search algorithms in Java applications, it is critical to analyze the individual features of the data as well as the requirements of the search operation.
Applications
Interpolation search is a search algorithm in Java that can be used in various contexts when sorted data is available. Interpolation search in Java has the following potential applications:
Interpolation search can help find values in massive sorted datasets like sorted arrays or lists. Compared to binary search, its ability to predict the position of the target value based on the values of the first and last elements in the dataset can result in faster convergence toward the target value.
In Java programs that connect with databases, interpolation search can be used to look for specific values in massive sorted datasets, such as indexed columns in database tables. Depending on the properties of the data and the database indexing approach, it may provide faster search performance than other search algorithms.
Interpolation search can be utilized in numerical computations in Java when searching sorted arrays or lists of numerical values for specified target values. Interpolation search, for example, can be used in scientific computing or financial applications to efficiently locate values in sorted arrays or lists of data points for interpolation or approximation purposes.
Interpolation search can be utilized in scientific applications when enormous datasets are sorted, and specific values must be looked for. Interpolation search, for example, can be used to effectively search through sorted datasets of measurements, observations, or simulations to extract helpful information in domains such as geophysics, bioinformatics, or meteorology.
Interpolation search can improve speed in Java applications that require it, such as real-time systems or high-performance computing applications. Its promise for quicker search performance on evenly dispersed data compared to other search algorithms can be used to optimize search operations in performance-critical settings.
Conclusion
Finally, searching and sorting algorithms are essential Java tools for efficiently organizing and retrieving data. Java includes several built-in searching and sorting algorithms that are performance-optimized and integrated with the Java Collections Framework. These algorithms provide benefits such as enhanced performance, flexibility, ease of use, stability, and applicability across various fields.
However, the suitable method is chosen based on data properties, application needs, and available system resources. Understanding the advantages and disadvantages of different Java searching and sorting algorithms is critical for designing effective and dependable data manipulation solutions in Java applications.
Read Also - Exception Handling in Java with Examples