🎓 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
In this blog post, we will discuss how to find the ceiling of a given number in a sorted array. The ceiling of a number x is the smallest element in the array greater than or equal to x. This problem is a variation of binary search.
Problem
Given a sorted array and a value x, find the ceiling of x in the array. If the ceiling doesn’t exist, output -1.
Example 1:
Input: a[] = {1, 3, 9, 15, 15, 18, 21}, x = 0
Output: 1
Example 2:
Input: a[] = {1, 3, 9, 15, 15, 18, 21}, x = 1
Output: 1
Example 3:
Input: a[] = {1, 3, 9, 15, 15, 18, 21}, x = 5
Output: 9
Example 4:
Input: a[] = {1, 3, 9, 15, 15, 18, 21}, x = 25
Output: -1
2. Solution Steps
1. Use binary search to find the ceiling.
2. If the current element is greater than or equal to x, check if it’s the ceiling.
3. Continue the search in the left sub-array if the current element is greater than x.
4. Continue the search in the right sub-array if the current element is less than x.
5. If x is greater than all elements, return -1.
3. Code Program
public class Solution {
// Main method for testing
public static void main(String[] args) {
int[] a = {1, 3, 9, 15, 15, 18, 21};
System.out.println("Ceiling of 0: " + findCeiling(a, 0));
System.out.println("Ceiling of 1: " + findCeiling(a, 1));
System.out.println("Ceiling of 5: " + findCeiling(a, 5));
System.out.println("Ceiling of 25: " + findCeiling(a, 25));
}
// Method to find the ceiling in a sorted array
public static int findCeiling(int[] a, int x) {
int start = 0, end = a.length - 1;
int res = -1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (a[mid] == x) return a[mid];
if (a[mid] < x) {
start = mid + 1;
} else {
res = a[mid];
end = mid - 1;
}
}
return res;
}
}
Output:
Ceiling of 0: 1 Ceiling of 1: 1 Ceiling of 5: 9 Ceiling of 25: -1
Explanation:
The findCeiling method performs a binary search to find the ceiling of x.
For the input array [1, 3, 9, 15, 15, 18, 21], it finds the smallest element greater than or equal to x.
For x = 0, 1 is the ceiling; for x = 1, the ceiling is still 1; for x = 5, the ceiling is 9; and for x = 25, there is no ceiling (hence -1).
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