C++ Standard Template Library (STL) provides several inbuilt functions to perform binary search on arrays and containers. Here are some of them:

binary_search(start, end, num): This function returns boolean true if the element is found in the range [start, end), otherwise returns false.

lower_bound(start, end, num): This function returns an iterator pointing to the first element in the range [start, end) which has a value not less than ‘num’. It returns end if no such element exists.

upper_bound(start, end, num): This function returns an iterator pointing to the first element in the range [start, end) which has a value greater than ‘num’. It returns end if no such element exists.

Here is an example of how to use these functions:

#include<bits/stdc++.h> using namespace std; int main(){ int arr[] = {1, 3, 4, 4, 6, 6}; int n = sizeof(arr)/sizeof(arr[0]); // Check if 4 is present if (binary_search(arr, arr+n, 4)) cout << "4 is present"; else cout << "4 is not present"; // Find first occurrence of 4 auto lb = lower_bound(arr, arr+n, 4); cout << "First occurrence of 4 is at index " << (lb - arr); // Find last occurrence of 4 auto ub = upper_bound(arr, arr+n, 4); cout << "Last occurrence of 4 is at index " << (ub - arr - 1); return 0; }

In this example, binary_search checks if 4 is present in the array. lower_bound finds the first occurrence of 4, and upper_bound finds the last occurrence of 4.

Question

C++ Standard Template Library (STL) provides several inbuilt functions to perform binary search on arrays and containers. Here are some of them:

1. `binary_search(start, end, num)`: This function returns boolean true if the element is found in the range [start, end), otherwise returns false.

2. `lower_bound(start, end, num)`: This function returns an iterator pointing to the first element in the range [start, end) which has a value not less than ‘num’. It returns end if no such element exists.

3. `upper_bound(start, end, num)`: This function returns an iterator pointing to the first element in the range [start, end) which has a value greater than ‘num’. It returns end if no such element exists.

Here is an example of how to use these functions:

```cpp
#include<bits/stdc++.h>
using namespace std;

int main(){
    int arr[] = {1, 3, 4, 4, 6, 6};
    int n = sizeof(arr)/sizeof(arr[0]);

// Check if 4 is present
    if (binary_search(arr, arr+n, 4))
       cout << "4 is present"; 
    else
       cout << "4 is not present";

// Find first occurrence of 4
    auto lb = lower_bound(arr, arr+n, 4);
    cout << "First occurrence of 4 is at index " << (lb - arr);

// Find last occurrence of 4
    auto ub = upper_bound(arr, arr+n, 4);
    cout << "Last occurrence of 4 is at index " << (ub - arr - 1);

return 0;
}
```

In this example, `binary_search` checks if 4 is present in the array. `lower_bound` finds the first occurrence of 4, and `upper_bound` finds the last occurrence of 4.

Knowee AI · Accepted Answer