﻿

# Lowerbound, upperbound when element is existed or non-existed

Dec 5th, 2020
950
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include "bits/stdc++.h"
2. using namespace std;
3.
4. int lower_bound(int arr[], int n, int X) {
5.     int l = 0;
6.     int r = n;
7.
8.     // Till low is less than high
9.     while (l < r) {
10.         int mid = (l+r)/2;
11.
12.         // If X is less than or equal
13.         // to arr[mid], then find in
14.         // left subarray
15.         if (X <= arr[mid]) {
16.             r = mid;
17.         }
18.
19.         // If X is greater arr[mid]
20.         // then find in right subarray
21.         else {
22.             l = mid + 1;
23.         }
24.     }
25.
26.     // Return the lower_bound index
27.     return l;
28. }
29.
30. int upper_bound(int arr[], int n, int X) {
31.     int l = 0;
32.     int r = n;
33.
34.     // Till low is less than high
35.     while (l < r) {
36.         // Find the middle index
37.         int mid = (l+r)/2;
38.
39.         // If X is greater than or equal
40.         // to arr[mid] then find
41.         // in right subarray
42.         if (X >= arr[mid]) {
43.             l = mid + 1;
44.         }
45.
46.         // If X is less than arr[mid]
47.         // then find in left subarray
48.         else {
49.             r = mid;
50.         }
51.     }
52.
53.     // Return the upper_bound index
54.     return l;
55. }
56.
57. // Function to implement lower_bound
58. // and upper_bound of X
59. void printBound(int arr[], int n, int X) {
60.     int idx;
61.
62.     // If lower_bound doesn't exists
63.     if (lower_bound(arr, n, X) == n) {
64.         printf("Lower bound doesn't exist");
65.     }
66.     else {
67.         // Find lower_bound
68.         idx = lower_bound(arr, n, X);
69.         printf("Lower bound of %d is %d at index % d\n ", X, arr[idx], idx);
70.     }
71.
72.     // If upper_bound doesn't exists
73.     if (upper_bound(arr, n, X) == n) {
74.         printf("Upper bound doesn't exist");
75.     }
76.     else {
77.         // Find upper_bound
78.         idx = upper_bound(arr, n, X);
79.         printf("Upper bound of %d is %d at index % d\n ", X, arr[idx], idx);
80.     }
81. }
82.
83. int main() {
84.     int arr[] = { 4, 6, 10, 12, 18, 20 };
85.     int n = sizeof(arr) / sizeof(arr[0]);
86.
87.     // Element whose lower bound and
88.     // upper bound to be found
89.     int X = 6;
90.
91.     // Function Call
92.     printBound(arr, n, X);
93.
94.     printBound(arr, n, 7);
95.     return 0;
96. }
97.
98.
99. /*
100. eikhane amader r=n newa lage karon output jokhon n asbe tokhon bujhte parobo je array te lowerbound/ upperbound exist kore nah
101. */
RAW Paste Data