C++ Algorithms and Binary Search Implementation Codes

Posted on Oct 5, 2026 in Computers

C++ Binary Search and Algorithms Collection

1. Binary Search Implementation

#include <iostream> 
using namespace std;
int main(){
    int n; 
    cin >> n;
    int a[100000];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int x;
    cin >> x;
    int l = 0, r = n - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (a[m] == x) {
            cout << "Yes";
            return 0;
        }
        if (a[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }
    cout << "No";
    return 0;
}

2. Range Queries on Array Elements

#include <iostream>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;

    int a[100];

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;

        int ans = 0;

        for (int i = 0; i < n; i++) {
            if ((a[i] >= l1 && a[i] <= r1) ||
                (a[i] >= l2 && a[i] <= r2)) {
                ans++;
            }
        }

        cout << ans << endl;
    }

    return 0;
}

3. Prefix Sums and Binary Search

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    long long a[200000];
    long long sum = 0;

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;

        sum += x;
        a[i] = sum;
    }

    while (m--) {
        long long x;
        cin >> x;

        int l = 0, r = n - 1;

        while (l < r) {
            int mid = (l + r) / 2;

            if (a[mid] >= x)
                r = mid;
            else
                l = mid + 1;
        }

        cout << l + 1 << endl;
    }

    return 0;
}

4. Frequency Counting and Summation Arrays

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int cnt[1001] = {};
    long long sum[1001] = {};

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        cnt[x]++;
        sum[x] += x;
    }

    for (int i = 1; i <= 1000; i++) {
        cnt[i] = cnt[i] + cnt[i - 1];
        sum[i] = sum[i] + sum[i - 1];
    }

    int p;
    cin >> p;

    while (p--) {
        int x;
        cin >> x;

        cout << cnt[x] << " " << sum[x] << endl;
    }

    return 0;
}

5. Advanced Range Counting with STL

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

vector<long long> a;

long long countRange(long long l, long long r){
     return upper_bound(a.begin(), a.end(), r) - lower_bound(a.begin(), a.end(), l);
}

int main(){
   ios::sync_with_stdio(false);
   cin.tie(0);
   int n, q;
   cin >> n >> q;
   a.resize(n);
   for(int i = 0; i < n; i++) cin >> a[i];
   sort(a.begin(), a.end());
   while(q--){
      long long l1, r1, l2, r2;
      cin >> l1 >> r1 >> l2 >> r2;
      long long ans;
      if(r1 < l2 || r2 < l1){
           ans = countRange(l1, r1) + countRange(l2, r2);
      } else {
         ans = countRange(min(l1, l2), max(r1, r2));
      }
      cout << ans << "\n";
   }
}

6. Binary Search on Answer: Bananas and Hours

#include <iostream>
using namespace std;

int main() {
    int n;
    long long h;
    cin >> n >> h;

    long long a[10000];
    long long l = 1, r = 0;

    for (int i = 0; i < n; i++) {
        cin >> a[i];

        if (a[i] > r)
            r = a[i];
    }

    while (l < r) {
        long long m = (l + r) / 2;
        long long hours = 0;

        for (int i = 0; i < n; i++)
            hours += (a[i] + m - 1) / m;

        if (hours <= h)
            r = m;
        else
            l = m + 1;
    }

    cout << l;

    return 0;
}

7. Floating Point Binary Search

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

int n;
long long k;
vector<double> a;

bool check(double len) {
    long long cnt = 0;

    for (double x : a) {
        cnt += (long long)(x / len);

        if (cnt >= k)
            return true;
    }

    return false;
}

int main() {
    cin >> n >> k;

    a.resize(n);

    double hi = 0;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        hi = max(hi, a[i]);
    }

    double lo = 0;

    for (int it = 0; it < 100; it++) {
        double mid = (lo + hi) / 2;

        if (check(mid))
            lo = mid;
        else
            hi = mid;
    }

    cout << fixed << setprecision(9) << lo << endl;

    return 0;
}