Searching Algorithms In Java DS
What are searching algorithms?
In Java DS, Searching algorithms are used to find an element in a collection and obtain its location (index) in the collection.
If the element is present in the collection, give its location otherwise give -1 or null indicating that the element is not found or not present in the collections.
Linear search
Linear Search is the basic searching algorithm where the element to search is checked against all the elements in the collections or array and is also known as sequential search.
Linear search can be used in sorted and unsorted arrays.
In the below image we have an unsorted list and search for element 40. Starting from the first element arr[0] we compare the element with x and keep on traversing till x is found.
We have found the x (40) in index 5 so we stop further searching and return the index.
How to implement linear search
- Start from the first element array[0] and iterate through all elements, comparing each element with x.
- If x matches the element, return the element index.
- If x does not match any elements, return -1.
import java.util.Arrays;
public class LinearSearch {
public static void main(String[] args) {
int[] arr = new int[] {
1, 5, 3, 4, 2, 6, 7, 8
};
int element = 2;
int index = linearSearch(arr, element);
if (index != -1) {
System.out.println("Element " + element + " found at index " + index);
} else {
System.out.println("Element not found in array " + Arrays.toString(arr));
}
}
public static int linearSearch(int[] arr, int element) {
int len = arr.length;
for (int i = 0; i<len; i++) {
if (element == arr[i]) {
return i;
}
}
return -1;
}
}
The time complexity of linear search depends on the size and position of the element. For example, the element can be found at the start of the list, and in some cases, the element can be found at the last of the list.
When to use Linear search
Linear Search works on any list whether it’s sorted or unsorted. It is useful when the array is small and contains limited elements.
Binary Search
Binary search work only with sorted array and we need to first convert unsorted array to sorted for our binary search to work.
It follows the divide and conquer approach where the list is divided into two halves each time.
The search is always performed on the middle portion of the array, where the middle portion is calculated based on the following format.
middle = ( beginning + end ) / 2
or
middle = ( low + high ) / 2
Consider this example, which is a sorted array.
First the low is 0 and the high is 9 which are index values so the middle value is 4. The element present in arr[4] is 50 which is not the target element 60.
Now 60 is greater than arr[4] 50 so we will go for the left portion of the array.
Low is 5 and high is 9, the middle is 7. Again, the arr[7] is not equal to 60 but ar[7] = 80 is greater than 60. Therefore, we go to the right portion of the array
Now low is 5 and high is 6, the middle is 5 and the arr[5] is 60. On index 5, we found the target element.
How to implement binary search
- If the given array is not sorted, sort it.
- Calculate the middle value using the above formula.
- If the array[middle] is the same value as the target, then return the middle value.
- If the target element is greater than array[middle] then low = mid+1 else high = mid-1.
- Repeat steps 2 to 4 until low<= high.
We can implement binary search in two ways.
- Iterative method
- Recursive method
First, let's implement an iterative way of implementing a binary search algorithm.
import java.util.Arrays;
public class BinarySearch {
public static void main(String[] args) {
int[] arr = new int[] {
1, 5, 3, 4, 2, 6, 7, 8
};
int element = 3;
int low = 0;
int high = arr.length - 1;
Arrays.sort(arr);
System.out.println("Sorted Array " + Arrays.toString(arr));
int index = binarySearch(arr, low, high, element);
if (index != -1) {
System.out.println("Element " + element + " found at index " + index);
} else {
System.out.println("Element not found in array " + Arrays.toString(arr));
}
}
public static int binarySearch(int[] arr, int element) {
int low = 0;
int high = arr.length - 1;
do {
int mid = (low + high) / 2;
if (arr[mid] == element) {
return mid;
} else if (element > arr[mid]) // x is on the right side
{
low = mid + 1;
} else // x is on the left side
{
high = mid - 1;
}
} while (low<= high);
return -1;
}
}
Now we will see the recursive way of implementing binary search.
import java.util.Arrays;
public class BinarySearch {
public static void main(String[] args) {
int[] arr = new int[] {
1, 5, 3, 4, 2, 6, 7, 8
};
int element = 3;
int low = 0;
int high = arr.length - 1;
Arrays.sort(arr);
System.out.println("Sorted Array " + Arrays.toString(arr));
int index = binarySearch(arr, low, high, element);
if (index != -1) {
System.out.println("Element " + element + " found at index " + index);
} else {
System.out.println("Element not found in array " + Arrays.toString(arr));
}
}
public static int binarySearch(int[] arr, int low, int high, int element) {
if (high >= low) {
int mid = (low + high) / 2;
if (arr[mid] == element) {
return mid;
}
if (element > arr[mid]) {
return binarySearch(arr, mid + 1, high, element);
} else {
return binarySearch(arr, low, mid - 1, element);
}
}
return -1;
}
}
When to use binary search
Binary Search is useful when we want to search an element in a large sorted array with a fewer number of comparisons.
Jump Search
Jump Search also works only on the sorted array and its updated version of linear search. This is because the number of element comparisons with the target element is reduced by using a skip of the block.
We use a block size (m) to skip or jump a few array elements and once we find a block that contains the target element then use linear search in the block.
Block size ( m ) is used to reduce the number of searches. The value of M is determined by m = √n where n is the size of arrays.
We have sorted an array arr[] of size 10 so the block size m = 3.
If we compare arr[0] with target element 60, it does not match, so we go to the next block arr[m] where m is 3.
Now comparing arr[2] with 60 it does not match, so we move to the next block arr[2m].
The same arr[4] does not match the 60, so the next arr[6] contains 70, which is greater than 60.
So this block from arr[4] to arr[6] should contain our search element. Use linear search to this block to find the element positions.
How to implement jump search
- Calculate the block size (m) using array size.
- If array[0] is the target element, return 0.
- If array[m] is smaller than the search element, move on to the next block.
- If array[m] is greater than the search element, the current block contains the search element. Apply linear search and return the index.
- If the array does not contain the element, return -1.
package algorithms.search;
import java.util.Arrays;
public class JumpSearch {
public static void main(String[] args) {
int[] arr = new int[] {
1, 5, 3, 4, 2, 6, 7, 8, 9, 0
};
int element = 2;
Arrays.sort(arr);
System.out.println("Sorted Array " + Arrays.toString(arr));
int index = jumpSearch(arr, element);
if (index != -1) {
System.out.println("Element " + element + " found at index " + index);
} else {
System.out.println("Element not found in array " + Arrays.toString(arr));
}
}
public static int jumpSearch(int[] arr, int element) {
int arraySize = arr.length;
int blockSize = (int) Math.floor(Math.sqrt(arraySize));
System.out.println("Block Size " + blockSize);
if (arr[0] == element) {
return 0;
}
int m = blockSize;
while (m<= arraySize) {
if (arr[m] == element) {
return m;
} else if (arr[m] > element) {
break;
}
m += blockSize;
}
return linearSearch(arr, element, m - blockSize, m);
}
public static int linearSearch(int[] arr, int element, int blockStart, int blockEnd) {
for (int i = blockStart; i<= blockEnd; i++) {
if (element == arr[i]) {
return i;
}
}
return -1;
}
}
When to use jump search
It’s faster than linear search but slower than binary search and works only on the sorted lists.