Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Easy

Upper Bound C++

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Ever wondered how to quickly find a value in a sorted sequence, especially when you're looking for the smallest number greater than what you've got? That's where the concept of upper bound comes into play. 

Upper Bound C++

Common in C++ programming, the upper bound is a powerful tool used to optimize searches and data handling, making tasks smoother and more efficient for developers. This article will break down what upper bound is, look into its syntax, explore return types, and walk through examples to solidify your understanding. 

Syntax

The upper bound in C++ is a function that can be used with any sorted sequence, like arrays or vectors. It's part of the Standard Template Library (STL), which is like a toolbox for developers, packed with ready-to-use functions for common tasks. To use the upper bound, you first need to know its syntax, which is the way you write the command so your computer understands it.

Here's how it looks:

upper_bound(start, end, value);

 

  • start: This is where your search begins. It's like telling someone to start looking from the beginning of a line.
     
  • end: This marks the end of your search area. It's like saying, "Stop looking once you reach the end of the line."
     
  • value: This is the number you're looking for. But instead of finding this number, the upper bound gives you the first number that's bigger than this.
     

Imagine you have a row of numbers, and you're looking for the first spot where you can place a new number so that the row stays in order. That's what the upper bound helps you with.

  • C++

C++

#include <iostream>
#include <vector>
#include <algorithm> // This is where upper_bound comes from

using namespace std;

int main() {
vector<int> numbers = {1, 3, 5, 7, 9};
int value = 6;
auto it = upper_bound(numbers.begin(), numbers.end(), value);
cout << "The first number greater than " << value << " is at position: " << (it - numbers.begin()) << endl;
return 0;
}

Output

The first number greater than 6 is at position: 3


In this code, we're using upper_bound to find the first number greater than 6 in a list of numbers. The auto keyword lets the compiler figure out the type of the it variable, which points to the place in the sequence where the number would fit.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Return Type

When you use the upper bound function in C++, it's helpful to know what you'll get back from it. This is called the "return type." For the upper bound, the return type is a bit like a finger pointing to a spot in your list of numbers. It doesn't give you the number itself but shows you where the number would go if it was in the list.

In technical terms, the upper bound function returns an iterator. Think of an iterator as a marker or a pointer that shows a specific position in your sorted sequence, like a bookmark in your notebook. If the upper bound finds a number greater than the one you're looking for, the iterator will point right there. If there's no number bigger than yours in the list, the iterator will point to the end, signaling there's no spot for your number.

Here's a quick example to make it clearer:

  • C++

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
vector<int> numbers = {2, 4, 6, 8, 10};
int value = 7;

auto it = upper_bound(numbers.begin(), numbers.end(), value);

if (it != numbers.end()) {
cout << "The first number greater than " << value << " is: " << *it << endl;
} else {
cout << "There's no number greater than " << value << " in the list." << endl;
}

return 0;
}

Output

The first number greater than 7 is: 8


In this code, we're looking for the first number greater than 7. The upper bound function tells us the position of this number. We use *it to get the number at this position. If it is the same as numbers.end(), it means our number is bigger than any in the list, so there's no upper bound in the sequence.

Examples

Understanding the upper bound with examples can make things a lot clearer. Let's walk through a couple of scenarios where the upper bound function in C++ comes in handy. This will help you see how you might use it in your own coding projects.

Example 1: Finding the Upper Bound in a List of Numbers

Imagine you have a list of numbers sorted in ascending order, like this: 1, 2, 4, 4, 5, 7, 8. You want to find the first number that is greater than 4. Using the upper bound function, you can easily locate this number.

Here's how you could write your code:

  • C++

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
vector<int> numbers = {1, 2, 4, 4, 5, 7, 8};
int value = 4;

auto it = upper_bound(numbers.begin(), numbers.end(), value);

if (it != numbers.end()) {
cout << "The first number greater than " << value << " is: " << *it << endl;
} else {
cout << "No number is greater than " << value << " in the list." << endl;
}

return 0;
}

Output

The first number greater than 4 is: 5


In this example, the upper bound function will find the number 5, because it's the first number greater than 4 in the list.

Example 2: Using Upper Bound with Custom Objects

Let's say you're working with a list of books, and each book has a page count. You want to find the first book with more than 300 pages. First, you'll need to sort your books by page count. Then, you can use the upper bound function to find the first book that meets your criteria.

Here's an example of how this could look in code:

  • C++

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Book {
public:
string title;
int pageCount;

Book(string t, int p) : title(t), pageCount(p) {}
};

bool compareByPageCount(const Book& a, const Book& b) {
return a.pageCount < b.pageCount;
}

int main() {
vector<Book> books = {
Book("Book A", 250),
Book("Book B", 320),
Book("Book C", 150),
Book("Book D", 500),
};

sort(books.begin(), books.end(), compareByPageCount);

int targetPageCount = 300;
auto it = upper_bound(books.begin(), books.end(), targetPageCount, [](int pageCount, const Book& book) {
return pageCount < book.pageCount;
});

if (it != books.end()) {
cout << "The first book with more than " << targetPageCount << " pages is: " << it->title << endl;
} else {
cout << "No book has more than " << targetPageCount << " pages." << endl;
}

return 0;
}

Output

The first book with more than 300 pages is: Book B


In this scenario, the upper bound function helps you quickly find the first book with more than 300 pages, which is "Book B" with 320 pages.

Frequently Asked Questions

What happens if all elements in the sequence are less than the value?

If every element in your sequence is less than the value you're comparing with, the upper bound function will point to the end of the sequence. This means there's no element greater than your specified value.

Can upper bound be used with non-numeric data, like strings?

Yes, the upper bound function works with any data type that can be sorted and compared, including strings. It's great for finding the insertion point for a specific value in a sorted list of strings.

Is upper bound different from lower bound?

Yes, there's a difference. While the upper bound finds the first element greater than a given value, the lower bound finds the first element not less than (i.e., greater or equal to) the given value. They are similar but used for slightly different purposes.

Conclusion

In this article, we have learned about the upper bound function in C++ & its practical applications. Starting with the basics, we explored the syntax, which shows how to use the function in your code. We then looked into the return type, explaining that upper bound returns an iterator pointing to the first element greater than a given value in a sorted sequence.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Topics covered
1.
Introduction
2.
Syntax
2.1.
C++
3.
Return Type
3.1.
C++
4.
Examples
4.1.
Example 1: Finding the Upper Bound in a List of Numbers
4.2.
C++
4.3.
Example 2: Using Upper Bound with Custom Objects
4.4.
C++
5.
Frequently Asked Questions
5.1.
What happens if all elements in the sequence are less than the value?
5.2.
Can upper bound be used with non-numeric data, like strings?
5.3.
Is upper bound different from lower bound?
6.
Conclusion