Lower Bound-STL in C++ hackerrank solution

Problem statement:

You are given a sorted list of integers and a number.

Your task is to write a function that performs a lower bound search on the list and returns the index of the first occurrence of the number.

If the number is not present in the list, it should return the index where the number should be inserted to maintain the sorted order.

      
Sample Input:
The input consists of two lines: 



The first line contains an integer N, representing the number of elements in the list.


The second line contains N space-separated integers, representing the elements of the list.


The third line contains an integer Q, representing the number of queries.


The next Q lines contain a single integer x, representing the number to search for in the list.


5
1 2 4 4 6
3
0
4
7

      
Sample Output:
For each query, print a single integer on a new line: 



If the number is found in the list, print the index of its first occurrence. 


If the number is not found in the list, print the index where it should be inserted.


0
2
5

Explanation:

In this example, we have 5 elements in the list: [1, 2, 4, 4, 6].

For the first query, the number 0 is not present in the list. The sorted order should be [0, 1, 2, 4, 4, 6], so it should be inserted at index 0.

For the second query, the number 4 is present in the list. Its first occurrence is at index 2.

For the third query, the number 7 is not present in the list. The sorted order should be [1, 2, 4, 4, 6, 7], so it should be inserted at index 5.

      
  #include <iostream>
  #include <vector>  
  #include <algorithm>
  
  using namespace std;
  
  int main() {
      int N;
      cin >> N;
  
      vector arr(N);
      for (int i = 0; i < N; i++) {
          cin >> arr[i];
      }
  
      int Q;
      cin >> Q;
  
      while (Q--) {
          int x;
          cin >> x;
  
          vector::iterator lb = lower_bound(arr.begin(), arr.end(), x);
  
          if (*lb == x) {
              cout << lb - arr.begin() << endl;
          } else {
              cout << lb - arr.begin() << endl;
          }
      }
  
      return 0;
  }
  

Code Explanation

We start by including the necessary header files, including for input/output operations, for using the vector container, and for the lower_bound function.

In the main() function, we read the number of elements in the list (N) using cin.

We then create a vector arr of integers with size N to store the elements of the list.

Using a for loop, we read the elements of the list and store them in the vector arr.

Next, we read the number of queries (Q) using cin.

We iterate Q times, and in each iteration, we read a single integer x using cin.

We use the lower_bound function to perform a lower bound search on the vector arr for the number x. This function returns an iterator pointing to the first element in the range that is not less than x.

We check if the value at the lower bound iterator is equal to x. If it is, we print the index of its first occurrence by subtracting the lower bound iterator from the beginning iterator of the vector arr.

If the value at the lower bound iterator is not equal to x, it means x is not present in the list. We still print the index of the lower bound iterator to indicate where x should be inserted to maintain the sorted order.

Finally, we return 0 to indicate successful execution of the program.

This solution uses the lower_bound function from the library to efficiently perform the lower bound search. It leverages the fact that the list is sorted, which allows for an efficient search in logarithmic time complexity.

I hope this explanation helps you understand the problem, the solution, and the code implementation. Let me know if you have any further questions!