📘 Premium Read: Access my best content on Medium member-only articles — deep dives into Java, Spring Boot, Microservices, backend architecture, interview preparation, career advice, and industry-standard best practices.
✅ Some premium posts are free to read — no account needed. Follow me on Medium to stay updated and support my writing.
🎓 Top 10 Udemy Courses (Huge Discount): Explore My Udemy Courses — Learn through real-time, project-based development.
▶️ Subscribe to My YouTube Channel (172K+ subscribers): Java Guides on YouTube
Let's get started with what is searching for ? and why do we need searching ?.
What is Searching?
Why do we need Searching?
Searching Algorithms
- Linear Search Algorithm
- Binary Search Algorithm
- Interpolation Search Algorithm
1. Linear Search Algorithm
/**
* In computer science, linear search or sequential search is a method for
* finding a target value within a list. It sequentially checks each element of
* the list for the target value until a match is
* found or until all the elements have been searched.
* <p>
* Worst-case performance O(n)<br>
* Best-case performance O(1)<br>
* Average performance O(n)<br>
* Worst-case space complexity O(1)<br>
* <p>
* @see <a href="https://en.wikipedia.org/wiki/Linear_search">Linear Search (Wikipedia)</a>
* <br>
* @author Ramesh Fadatare
*/
public class LinearSearch {
public static final int unorderedLinearSearch(int value, int[] array) {
for (int i = 0; i < array.length; i++) {
int iValue = array[i];
if (value == iValue)
return i;
}
return Integer.MAX_VALUE;
}
public static final int orderedLinearSearch(int value, int[] array) {
for (int i = 0; i < array.length; i++) {
if (value == array[i]){
return i;
}
else if (array[i] > value){
return -1;
}
}
return Integer.MAX_VALUE;
}
public static void main(String[] args) {
int[] integers = {1,2,3,4,5,6,7,8,8,8,9,9,9,0};
//the element that should be found
int shouldBeFound = 9;
int atIndex = LinearSearch.unorderedLinearSearch(shouldBeFound, integers);
System.out.println(String.format("Should be found: %d. Found %d at index %d. An array length %d"
, shouldBeFound, integers[atIndex], atIndex, integers.length));
int[] sortedArray = {10,20,30,40,50};
//the element that should be found
int key = 30;
atIndex = LinearSearch.orderedLinearSearch(key, sortedArray);
System.out.println(String.format("Should be found: %d. Found %d at index %d. An array length %d"
, key, sortedArray[atIndex], atIndex, sortedArray.length));
}
}
Should be found: 9. Found 9 at index 10. An array length 14
Should be found: 30. Found 30 at index 2. An array length 5
Read more about linear search algorithms on Linear Search Algorithm in Java
2. Binary Search Algorithm
Binary Search Implementation using Java
- Iterative implementation
- Recursive Implementation
- Using Arrays.binarySearch()
- Using Collections.binarySearch()
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);
}
}
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);
}
}
Search element 6 found in location index : 7
Recursive Implementation
Now, let’s have a look at a simple, recursive implementation as well:
public class BinarySearch {
public int binarySearchRecursively(int[] sortedArray, int key, int low, int high) {
int middle = (low + high) / 2;
if (high < low) {
return -1;
}
if (key == sortedArray[middle]) {
return middle;
} else if (key < sortedArray[middle]) {
return binarySearchRecursively(sortedArray, key, low, middle - 1);
} else {
return binarySearchRecursively(sortedArray, key, middle + 1, high);
}
}
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.binarySearchRecursively(sortedArray, key, 0, sortedArray.length -1);
System.out.println("Search element found in location index : " + index);
}
}
public class BinarySearch {
public int binarySearchRecursively(int[] sortedArray, int key, int low, int high) {
int middle = (low + high) / 2;
if (high < low) {
return -1;
}
if (key == sortedArray[middle]) {
return middle;
} else if (key < sortedArray[middle]) {
return binarySearchRecursively(sortedArray, key, low, middle - 1);
} else {
return binarySearchRecursively(sortedArray, key, middle + 1, high);
}
}
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.binarySearchRecursively(sortedArray, key, 0, sortedArray.length -1);
System.out.println("Search element found in location index : " + index);
}
}
Search element found in location index : 7
Using Arrays.binarySearch()
public class BinarySearch {
public int runBinarySearchUsingJavaArrays(int[] sortedArray, Integer key) {
int index = Arrays.binarySearch(sortedArray, key);
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 index1 = binSearch.runBinarySearchUsingJavaArrays(sortedArray, key);
System.out.println("Search element found in location index : " + index1);
}
}
public class BinarySearch {
public int runBinarySearchUsingJavaArrays(int[] sortedArray, Integer key) {
int index = Arrays.binarySearch(sortedArray, key);
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 index1 = binSearch.runBinarySearchUsingJavaArrays(sortedArray, key);
System.out.println("Search element found in location index : " + index1);
}
}
Search element found in location index : 7
Using Collections.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);
}
}
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);
}
}
Search element found in location index : 7
T(n) = T(n/2) + c
Read more about binary search algorithms on Binary Search Algorithm in Java
3. Interpolation Search Algorithm
Interpolation Search Implementation in Java
/**
* Interpolation search is an algorithm for searching for a given key in an indexed array.
* @author Ramesh Fadatare
*/
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 = {10,20,30,40,50,60,70,80,90,100};
//the element that should be found
int key = 100;
InterpolationSearch search = new InterpolationSearch();
int atIndex = search.find(key, integers);
System.out.println("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);
}
}
Remember array index starts from 0
The size of the array is : 10
The element found at index : 9
Read more about Interpolation search algorithms on Interpolation Search Algorithm
Master in Data Structures and Algorithms in Java
Learn Complete Java Programming on Java Tutorial | Learn Java Programming with Examples
Comments
Post a Comment
Leave Comment