Arrays are most fundamental data structures in programming. Arrays are the contiguous memory blocks containing data of similar type.
In this blog, we will dive straight into array searching algorithms: Linear Search and Binary Search. We will also see some popular problems which we can solve using this algorithms.
Linear Search
Linear Search is a basic searching technique that scans through each element of the array until the target element is found.
Algorithm
Traverse the array from beginning to end.
Compare each element with the target element.
Return index of the target element if found else return -1 if the target is not present.
Implementation
public class LinearSearch {
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {3, 5, 7, 2, 8, 4};
int target = 7;
int result = linearSearch(arr, target);
if (result != -1) {
System.out.println("Element found at index: " + result);
} else {
System.out.println("Element not found");
}
}
}
Time Complexity
Best Case: O(1) -> If the target is the first element
Worst Case: O(n) -> If the target is the last element or not present
Binary Search
Binary Search is much faster than linear search but requires array to sorted. Binary Search only work when array is sorted either ascending order or descending order.
Algorithm
Set left=0 and right=size of array -1, Start by checking the middle element of the array.
If the middle element is smaller than the target element the focus on the right half otherwise focus on the left half of the array.
Repeat this process until you find the target element or the search window size becomes zero.
Implementation
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11};
int target = 7;
int result = binarySearch(arr, target);
if (result != -1) {
System.out.println("Element found at index: " + result);
} else {
System.out.println("Element not found");
}
}
}
Time Complexity
Best Case: O(1) -> If the target is the middle element
Worst Case: O(n) -> If the target is not present
Order-Agnostic Binary Search
Order-Agnostic Binary Search is a variant of Binary Search designed to work on arrays that can be sorted in either ascending or descending order. Before the main search, it determines the order of the array.
Algorithm
Check if the array is sorted in ascending or descending order by comparing the first and last elements.
Perform binary search accordingly:
For ascending order, move left or right as in regular Binary Search.
For descending order, reverse the comparison operators.
Implementation
public class OrderAgnosticBinarySearch {
public static int orderAgnosticBinarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
boolean isAscending = arr[left] < arr[right];
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (isAscending) {
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
if (arr[mid] > target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
public static void main(String[] args) {
int[] ascArr = {1, 3, 5, 7, 9};
int[] descArr = {9, 7, 5, 3, 1};
int target = 7;
int resultAsc = orderAgnosticBinarySearch(ascArr, target);
System.out.println(resultAsc != -1 ? "Element found at index: " + resultAsc : "Element not found");
int resultDesc = orderAgnosticBinarySearch(descArr, target);
System.out.println(resultDesc != -1 ? "Element found at index: " + resultDesc : "Element not found");
}
}
Time Complexity
Best Case: O(1) -> If the target is the middle element
Worst Case: O(n) -> If the target is not present
Popular Problems on Arrays
Ceiling Number
The smallest number in a sorted array greater than or equal to a given target.
Algorithm:
Use binary search.
If the target is not in the array, the left pointer will point to the ceiling after the loop.
Implementation
public class CeilingNumber {
public static int findCeiling(int[] nums, int target) {
int left = 0, right = nums.length - 1;
if (target > nums[right]) return -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return nums[mid];
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return nums[left];
}
}
Floor Number
The largest number in a sorted array less than or equal to a given target.
Algorithm:
Use binary search.
If the target is not in the array, the right pointer will point to the floor after the loop.
Implementation
public class FloorNumber {
public static int findFloor(int[] nums, int target) {
int left = 0, right = nums.length - 1;
if (target < nums[left]) return -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return nums[mid];
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return nums[right];
}
}
First and Last Occurrence
The first and last occurrence of a target in a sorted array.
- The array is sorted.
- The array contains duplicates.
- Find the first and last index of target element.
Ex. arr={1, 1, 3, 3, 5, 5, 5, 5, 6, 7} and target = 5
Therefore first index = 4 and last index = 7
Algorithm:
Use binary search to locate the target.
Adjust the left or right bounds to find the first and last occurrences.
Implementation
public class FirstAndLastOccurrence {
public static int[] searchRange(int[] nums, int target) {
int first = findBound(nums, target, true);
int last = findBound(nums, target, false);
return new int[]{first, last};
}
private static int findBound(int[] nums, int target, boolean isFirst) {
int left = 0, right = nums.length - 1, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
result = mid;
if (isFirst) right = mid - 1;
else left = mid + 1;
} else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return result;
}
}
Find the Position of an Element in an Infinite Sorted Array
Assume the lenght of array is infinite or you don’t know length of the array.
To apply binary search we should know the size of array so we can decide the size of search window (left, right)
So, The approach is start with limited window size 2 then exponentially increase it.
In first iteration window size will be 2 then declare left and right (left=0 and right=1)
If target element > arr[right] element then double the window size and set left = right+1 and right = right*2
Repeat until you find the window which contain target element.
Then simply apply binary search because now you the window size.
Algorithm:
Use an exponential search strategy to find a suitable range.
Apply binary search within the range.
Implementation
public class InfiniteArraySearch {
public static int searchInInfiniteArray(int[] nums, int target) {
int left = 0, right = 1;
while (nums[right] < target) {
left = right;
right *= 2;
}
return binarySearch(nums, target, left, right);
}
private static int binarySearch(int[] nums, int target, int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
}
Peak Index in a Mountain Array
A mountain array is an array of numbers that increases until a peak, then decreases until the end
Ex. Mountain array = {1, 2, 3, 4, 5, 6, 5, 4, 3} and Peak element = 6
Algorithm:
Use binary search.
Compare the middle element with its neighbors to determine the peak.
Implementation
public class MountainArray {
public static int peakIndexInMountainArray(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < arr[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
Find in Mountain Array
Search for a target in a mountain array.
Algorithm:
Locate the peak using binary search.
Search in the ascending and descending parts separately using binary search.
Implementation
public class FindInMountainArray {
public static int findInMountainArray(int[] arr, int target) {
int peak = peakIndexInMountainArray(arr);
int result = binarySearch(arr, target, 0, peak, true);
if (result != -1) return result;
return binarySearch(arr, target, peak + 1, arr.length - 1, false);
}
private static int binarySearch(int[] arr, int target, int left, int right, boolean isAscending) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (isAscending) {
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
} else {
if (arr[mid] > target) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}
public static int peakIndexInMountainArray(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < arr[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
Rotated Sorted Array
A rotated sorted array is an array where the elements are initially sorted in ascending order but have been rotated cyclically.
For example, the array {6, 7, 8, 1, 2, 3, 4, 5} is rotated and sorted, with the pivot at index 2.
Algorithm
Find the pivot:
Initialize Variables:
start = 0,end = array.length - 1.
Loop Until Start is Less Than or Equal to End:
While
start <= end:Calculate
mid = start + (end - start) / 2.Check Pivot Conditions:
If
array[mid] > array[mid + 1], returnarray[mid].If
array[mid - 1] > array[mid], returnarray[mid - 1].
Decide Which Half to Search:
If
array[mid] >= array[start]:- Move to the right:
start = mid + 1.
- Move to the right:
Else:
- Move to the left:
end = mid - 1.
- Move to the left:
Return -1:
- If no pivot is found (edge case for invalid input).
Now you know the pivot simply apply the binary search.
Binary Search in Segments
Perform a binary search in the left segment
[0, pivot].If the target is not found in the left segment, perform a binary search in the right segment
[pivot + 1, n - 1].
Return Result
If the target is found in either segment, return the index.
Otherwise, return
-1.
Implementation
class Solution {
public int search(int[] nums, int target) {
int pivot = findPivot(nums);
if (pivot == -1)
return binarySearch(nums, target, 0, nums.length - 1);
int left = binarySearch(nums, target, 0, pivot);
if (left != -1)
return left;
int right = binarySearch(nums, target, pivot + 1, nums.length - 1);
if (right != -1)
return right;
return -1;
}
public int binarySearch(int[] arr, int target, int start, int end) {
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
start = mid + 1;
else
end = mid - 1;
}
return -1;
}
public int findPivot(int[] arr) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (mid < end && arr[mid] > arr[mid + 1])
return mid;
if (mid > start && arr[mid] < arr[mid - 1])
return mid - 1;
if (arr[mid] <= arr[start])
end = mid - 1;
else
start = mid + 1;
}
return -1;
}
}