Day 13 of 100 Days of DSA Challenge: Searching Basics
Tushar Pant
Searching algorithms help locate specific elements or satisfy conditions within a dataset. Today’s tasks focused on Binary Search and its applications, solving problems efficiently by reducing the search space in each step. These exercises demonstrated how Binary Search is adapted for real-world scenarios.
1. Binary Search
Binary Search operates on sorted arrays by dividing the search interval in half repeatedly. It has a time complexity of O(logn), making it far more efficient than linear search for large datasets.
import java.util.Scanner;
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0, 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) {
Scanner sc = new Scanner(System.in);
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
System.out.println("Given Array: ");
for(int i : arr)
System.out.print(i+" ");
System.out.println();
System.out.print("Enter the target: ");
int index = binarySearch(arr, sc.nextInt());
System.out.println();
System.out.println("Target found at index: "+index);
}
}
2. Find the First and Last Position of an Element in a Sorted Array
This problem involves finding both the first and last occurrences of a target value in a sorted array. Binary Search is adapted to find these positions in O(log n) time by searching the left and right halves separately.
import java.util.Scanner;
public class FirstLastPosition {
public static int[] searchRange(int[] nums, int target) {
return new int[]{findPosition(nums, target, true), findPosition(nums, target, false)};
}
private static int findPosition(int[] nums, int target, boolean findFirst) {
int index = -1, left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
index = mid;
if (findFirst) right = mid - 1;
else left = mid + 1;
} else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return index;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 2};
System.out.println("Given Array: ");
for(int i : arr)
System.out.print(i+" ");
System.out.println();
System.out.print("Enter the target: ");
int[] ans = searchRange(arr, sc.nextInt());
System.out.println("First Position of target is at index: "+ans[0]);
System.out.println("Last position of target is at index: "+ans[1]);
}
}
3. Search in a Rotated Sorted Array
In a rotated sorted array, Binary Search is modified to account for the rotation. The key is identifying the sorted half of the array at each step and narrowing the search space accordingly.
import java.util.Scanner;
public class RotatedSortedArraySearch {
public static int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else {
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of the array:");
int n = sc.nextInt();
int[] nums = new int[n];
System.out.println("Enter the elements of the array:");
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
System.out.println("Enter the target element to search:");
int target = sc.nextInt();
int result = search(nums, target);
if (result != -1) {
System.out.println("Target found at index: " + result);
} else {
System.out.println("Target not found in the array.");
}
sc.close();
}
}
4. Find the Square Root of a Number Using Binary Search
The task is to find the integer part of the square root of a given number or the exact value up to a certain precision. Binary Search is used to repeatedly narrow the range of potential solutions, achieving O(logn) complexity.
import java.util.Scanner;
public class SquareRoot {
public static double sqrt(int x, double precision) {
double left = 0, right = x, mid = 0;
while (right - left > precision) {
mid = left + (right - left) / 2;
if (mid * mid <= x) left = mid;
else right = mid;
}
return left;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
double precision = 2;
System.out.println("Enter the number: ");
System.out.println("SquareRoot is: "+sqrt(sc.nextInt(), precision));
}
}
5. Find the Peak Element in an Array Using Binary Search
A peak element is greater than its neighbors. This problem can be solved using Binary Search by repeatedly halving the search space and moving toward the peak. The algorithm guarantees O(logn) complexity without requiring a sorted array.
import java.util.Scanner;
public class PeakElement {
public static int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) right = mid;
else left = mid + 1;
}
return left;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr = {1, 1, 2, 3, 4, 4, 4, 5};
System.out.println("Given Array: ");
for(int i : arr)
System.out.print(i+" ");
System.out.println();
System.out.println("Peak Element is: "+arr[findPeakElement(arr)]);
}
}
Reflection
Day 13 demonstrated the versatility of Binary Search, highlighting how it can solve complex problems efficiently when applied with modifications. Each problem today reinforced the importance of reducing problem scope intelligently, paving the way for even more advanced searching techniques. 🚀
Subscribe to my newsletter
Read articles from Tushar Pant directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by