🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
This blog post discusses how to efficiently find the starting and ending positions of a target value in a sorted array. This problem is a variant of binary search and requires an understanding of how to modify standard binary search to find boundary conditions.
Problem
Given an array a sorted in ascending order, find the starting and ending position of a given target value. If the target is not found in the array, return [-1, -1]. The solution must have O(log n) runtime complexity.
Example 1:
Input: a = [1, 4, 4, 10, 10, 15, 20], target = 10 Output: [3, 4]
Example 2:
Input: a = [1, 4, 4, 10, 10, 15, 20], target = 15 Output: [5, 5]
Example 3:
Input: a = [1, 4, 4, 10, 10, 15, 20], target = 0 Output: [-1, -1]
2. Solution Steps
1. Apply binary search to find the first occurrence of the target.
2. Apply binary search to find the last occurrence of the target.
3. Modify the binary search to adjust the search range based on the comparison with the target.
4. If the target is not found, return [-1, -1].
3. Code Program
public class Solution {
// Main method for testing
public static void main(String[] args) {
int[] a1 = {1, 4, 4, 10, 10, 15, 20};
System.out.println("First and last position of 10: " + Arrays.toString(searchRange(a1, 10)));
int[] a2 = {1, 4, 4, 10, 10, 15, 20};
System.out.println("First and last position of 15: " + Arrays.toString(searchRange(a2, 15)));
int[] a3 = {1, 4, 4, 10, 10, 15, 20};
System.out.println("First and last position of 0: " + Arrays.toString(searchRange(a3, 0)));
}
// Method to find the starting and ending position of a target value
public static int[] searchRange(int[] a, int target) {
int[] result = new int[]{-1, -1};
result[0] = findFirst(a, target);
result[1] = findLast(a, target);
return result;
}
// Helper method to find the first occurrence of target
private static int findFirst(int[] a, int target) {
int idx = -1;
int start = 0, end = a.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (a[mid] >= target) {
end = mid - 1;
} else {
start = mid + 1;
}
if (a[mid] == target) idx = mid;
}
return idx;
}
// Helper method to find the last occurrence of target
private static int findLast(int[] a, int target) {
int idx = -1;
int start = 0, end = a.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (a[mid] <= target) {
start = mid + 1;
} else {
end = mid - 1;
}
if (a[mid] == target) idx = mid;
}
return idx;
}
}
Output:
First and last position of 10: [3, 4] First and last position of 15: [5, 5] First and last position of 0: [-1, -1]
Explanation:
The searchRange method uses two binary searches: findFirst to locate the first occurrence of the target, and findLast to find the last occurrence.
For the array [1, 4, 4, 10, 10, 15, 20], the target 10 is found at indices 3 and 4, thus returning [3, 4].
For target 15, the method returns [5, 5], and for a non-existent target 0, it returns [-1, -1].
This approach efficiently solves the problem with O(log n) complexity.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment