Searching and Sorting in Java
Subject: Data Structures and Algorithms · Language: Java · Level: beginner · 6 min read
Practice linear search, binary search, Arrays.sort, and beginner-friendly sorting/searching logic.
Searching means finding whether a target value exists in a collection of data. Sorting means arranging values in a particular order, usually increasing or decreasing. Searching and sorting are connected because sorted data can often be searched faster. For example, binary search works only when data is sorted.
These two topics are important in DSA because many problems become easier after arranging data or quickly finding a required value.
Linear Search
Linear search checks elements one by one from the beginning to the end. It works on any array, whether the array is sorted or unsorted. Linear search is easy to understand and useful for small input or unsorted data. Its time complexity is O(n) because in the worst case we may need to check every element.
```java
int index = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
index = i;
break;
}
}
```
Here, `index` remains `-1` if the target is not found. If the target is found, we store its position and stop the loop using `break`.
Binary Search
Binary search repeatedly checks the middle element and removes half of the search space. This makes it much faster than linear search for large sorted arrays. Binary search only works correctly when the array is sorted. If the array is not sorted, the decision to move left or right becomes meaningless.
Its time complexity is O(log n) because the search space becomes half after every step.
```java
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; if (arr[mid] == target) {
break;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
``` The expression `left + (right - left) / 2` is commonly used to calculate the middle index safely.
Sorting in Java
Sorting arranges values in order. Java provides `Arrays.sort(arr)` to sort arrays quickly. For interviews, you should understand sorting concepts such as comparison, swapping, and order. But in many coding problems, using `Arrays.sort` is accepted and helps focus on the main logic.
```java
Arrays.sort(arr);
```
After this line, an integer array is arranged in increasing order.
Common Sorting Algorithms
Bubble sort repeatedly compares nearby elements and swaps them when they are in the wrong order. It is easy for beginners, but slow for large input. Selection sort repeatedly selects the smallest element from the unsorted part and places it at the correct position. It helps students understand the idea of choosing one correct element per pass.
Insertion sort builds the sorted part one element at a time. It works well for small or nearly sorted data and is useful for understanding how elements shift. Merge sort divides the array into smaller parts, sorts them, and merges them back. Quick sort chooses a pivot and rearranges elements around it. These two are important because they introduce divide-and-conquer thinking.
Beginners should first understand simple sorting logic like bubble, selection, and insertion. After that, merge sort and quick sort become easier because the foundation of comparison and ordering is already clear.
When to Sort
Sort when order helps the problem. Common examples include binary search, two-pointer problems, duplicate handling, ranking, interval problems, greedy problems, and finding closest pairs. Sorting changes the original order of the array. If the original order matters, make a copy before sorting or store indexes separately.
Arrays.sort and Arrays.binarySearch
`Arrays.sort(arr)` sorts the array. `Arrays.binarySearch(arr, target)` searches for a target in a sorted array. Remember that `Arrays.binarySearch` should be used after sorting, unless the array is already sorted.
```java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); System.out.print("Enter size: ");
int n = sc.nextInt();
int[] arr = new int[n]; System.out.print("Enter elements: ");
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
} System.out.print("Enter target: ");
int target = sc.nextInt();
Arrays.sort(arr); int index = Arrays.binarySearch(arr, target);
if (index >= 0) {
System.out.println("Found at index " + index + " after sorting");
} else {
System.out.println("Not found");
} System.out.print("Sorted array: ");
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
}
```
This program first reads the array, sorts it, and then searches for the target using binary search. The index printed is the index after sorting, not necessarily the original index before sorting.
Searching and Sorting in DSA
Searching is used when we need to find a value, position, count, or condition. Sorting is used when order can simplify the problem. Many DSA techniques depend on sorted data. Binary search, two pointers, greedy selection, and interval merging become easier after sorting.
Practice Question
Take an array and a target value as input. First search the target using linear search. Then sort the array and use binary search to check whether the target exists.