Searching Algorithms in Java
Searching is the process of finding a particular element (target/key) in a collection of data
such as an array, list, or database.
For example, given:
None
Array = [10, 25, 30, 45, 60]
Target = 45
A searching algorithm determines whether 45 exists and, if it does, returns its position/index.
1. Linear Search
Definition
Linear Search is the simplest searching algorithm. It checks each element one by one from the
beginning until:
● the target element is found, or
● all elements have been checked.
Example
None
Array: [10, 25, 30, 45, 60]
Index: 0 1 2 3 4
Target = 45
The algorithm checks:
None
10 → 25 → 30 → 45
The element is found at index 3.
Algorithm
None
1. Start from the first element.
2. Compare the current element with the target.
3. If they are equal, return the index.
4. Otherwise, move to the next element.
5. Repeat until the element is found or the array ends.
6. Return -1 if the element is not found.
Java Example
None
public class LinearSearch {
static int search(int[] arr, int target) {
for (int i = 0; i < [Link]; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] numbers = {10, 25, 30, 45, 60};
int target = 45;
int result = search(numbers, target);
if (result != -1) {
[Link]("Element found at index: " +
result);
} else {
[Link]("Element not found");
}
}
}
Output
None
Element found at index: 3
Complexity
Case Time Complexity
Best Case O(1)
Average O(n)
Case
Worst Case O(n)
Space O(1)
Advantages
● Very simple to implement.
● Works on sorted and unsorted data.
● Does not require additional memory.
● Suitable for small datasets.
Disadvantages
● Slow for large datasets.
● May need to examine every element.
2. Binary Search
Definition
Binary Search is an efficient searching algorithm that works by repeatedly dividing a sorted
array into two halves.
Important: Binary Search requires the data to be sorted.
Example
Consider:
None
Array = [10, 20, 30, 40, 50, 60, 70]
Target = 60
Initially:
None
10 20 30 40 50 60 70
↑
mid
Middle element = 40
Since:
None
60 > 40
Search only the right half:
None
50 60 70
Middle element = 60
Target found.
Algorithm
None
1. Set low = 0.
2. Set high = [Link] - 1.
3. Calculate middle:
mid = low + (high - low) / 2
4. Compare arr[mid] with target.
5. If arr[mid] == target:
Element found.
6. If target > arr[mid]:
Search right half.
7. If target < arr[mid]:
Search left half.
8. Repeat until low > high.
9. Return -1 if element is not found.
Java Example — Iterative Binary Search
None
public class BinarySearch {
static int search(int[] arr, int target) {
int low = 0;
int high = [Link] - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
}
if (target > arr[mid]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] numbers = {10, 20, 30, 40, 50, 60, 70};
int target = 60;
int result = search(numbers, target);
if (result != -1) {
[Link]("Element found at index: " +
result);
} else {
[Link]("Element not found");
}
}
}
Output
None
Element found at index: 5
Complexity
Case Time Complexity
Best Case O(1)
Average O(log n)
Case
Worst Case O(log n)
Space O(1)
Binary search is much faster than linear search for large sorted datasets.
3. Recursive Binary Search
Binary Search can also be implemented using recursion.
Java Example
None
public class RecursiveBinarySearch {
static int binarySearch(int[] arr, int low, int high, int
target) {
if (low > high) {
return -1;
}
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
}
if (target > arr[mid]) {
return binarySearch(arr, mid + 1, high, target);
}
return binarySearch(arr, low, mid - 1, target);
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50, 60, 70};
int target = 50;
int result = binarySearch(
arr,
0,
[Link] - 1,
target
);
[Link]("Index = " + result);
}
}
Output:
None
Index = 4
The recursive version has:
None
Time Complexity = O(log n)
Space Complexity = O(log n)
because recursive calls are stored on the call stack.