1) What is Binary Search Algorithm?
Binary search is a search algorithm used to find the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half until the target value is found or the interval is empty. The search interval is halved by comparing the target element with the middle value of the search space.
2) Conditions to apply Binary Search Algorithm in a Data Structure:
To apply Binary Search algorithm:
1.The data structure must be sorted. 2.Access to any element of the data structure takes constant time. 3) Binary Search Algorithm:
1.Compare the middle element of the search space with the key. 2.If the key is found at middle element, the process is terminated. 3.If the key is not found at middle element, choose which half will be used as the next search space. 4.If the key is smaller than the middle element, then the left side is used for next search. 5.If the key is larger than the middle element, then the right side is used for next search. 6.This process is continued until the key is found or the total search space is exhausted.
4) How does Binary Search Algorithm work?
To understand the working of binary search, consider the following illustration:
Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, and the target = 23.
First Step: Calculate the mid and compare the mid element with the key. If the key is less than mid element, move to left and if it is greater than the mid then move search space to the right.
1.Key (i.e., 23) is greater than current mid element (i.e., 16). The search space moves to the right.
2.Key is less than the current mid 56. The search space moves to the left.
3.If the key matches the value of the mid element, the element is found and stop search.
5) How to Implement Binary Search Algorithm?
The Binary Search Algorithm can be implemented in the following two ways
Iterative Binary Search Algorithm Recursive Binary Search Algorithm Given below are the pseudocodes for the approaches.
6) Iterative Binary Search Algorithm:
Here we use a while loop to continue the process of comparing the key and splitting the search space in two halves.
the
code// C++ program to implement iterative Binary Search
#include <bits/stdc++.h>
using namespace std;
// An iterative binary search function.
int binarySearch(int arr[], int low, int high, int x)
{
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if x is present at mid
if (arr[mid] == x)
return mid;
// If x greater, ignore left half
if (arr[mid] < x)
low = mid + 1;
// If x is smaller, ignore right half
else
high = mid - 1;
}
// If we reach here, then element was not present
return -1;
}
// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
Element is present at index 3
6) Complexity Analysis of Binary Search Algorithm:
Time Complexity: 1.Best Case: O(1) 2.Average Case: O(log N) 3.Worst Case: O(log N)
Auxiliary Space: O(1), If the recursive call stack is considered then the auxiliary space will be O(logN).
7) Applications of Binary Search Algorithm: 1.Binary search can be used as a building block for more complex algorithms used in machine learning, such as algorithms for training neural networks or finding the optimal hyperparameters for a model. 2.It can be used for searching in computer graphics such as algorithms for ray tracing or texture mapping. 3.It can be used for searching a database.
8) Advantages of Binary Search:
1.Binary search is faster than linear search, especially for large arrays. 2.More efficient than other searching algorithms with a similar time complexity, such as interpolation search or exponential search. 3.Binary search is well-suited for searching large datasets that are stored in external memory, such as on a hard drive or in the cloud.
9) Disadvantages of Binary Search: 1.The array should be sorted. 2.Binary search requires that the data structure being searched be stored in contiguous memory locations. 3.Binary search requires that the elements of the array be comparable, meaning that they must be able to be ordered.
after i send binary search information lets solve problem edu
step 1:
Binary search
Code#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
vector<int>v(n);
for(int i=0;i<n;i++)
{
cin>>v[i];
}
for(int i=0;i<k;i++)
{
int64_t x;
cin>>x;
int64_t l=0,r=n-1,mid;
bool balt=false;
while(l<=r)
{
mid=l+(r-l)/2;
if(v[mid]==x)
{
balt=true;
break;
}
else if(v[mid]<x)
{
l=mid+1;
}
else
r=mid-1;
}
if(balt)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
Closest to the Left
Code#include<bits/stdc++.h>
using namespace std;
int main()
{
int64_t n,k;
cin>>n>>k;
vector<int>v(n);
for(int i=0;i<n;i++)
{
cin>>v[i];
}
for(int i=0;i<k;i++)
{
int64_t x;
cin>>x;
auto it = upper_bound(v.begin(),v.end(),x);
cout<<it-v.begin()<<endl;
}
}
Closest to the Right
Code#include<bits/stdc++.h>
using namespace std;
int main()
{
int64_t n,k;
cin>>n>>k;
vector<int>v(n);
for(int i=0;i<n;i++)
{
cin>>v[i];
}
for(int i=0;i<k;i++)
{
int64_t x;
cin>>x;
auto it = lower_bound(v.begin(),v.end(),x);
cout<<it-v.begin()+1<<endl;
}
}
Fast Search
Code#include<bits/stdc++.h>
using namespace std;
int main()
{
int64_t n;
cin>>n;
vector<int64_t>v(n);
for(auto &i:v)
{
cin>>i;
}
sort(v.begin(),v.end());
int k;
cin>>k;
for(int i=0;i<k;i++)
{
int64_t l,r;
cin>>l>>r;
auto itl=lower_bound(v.begin(),v.end(),l);
auto itr=upper_bound(v.begin(),v.end(),r);
cout<<itr-itl<<" ";
}
cout<<endl;
}
step 2:
Packing Rectangles
Code#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool check(ll x,ll a,ll b,ll n)
{
return ((x/a)*(x/b))>=n;
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll a,b,n,l=0,r=1;
cin>>a>>b>>n;
while(!check(r,a,b,n))
r*=2;
while(l+1<r)
{
ll mid=(l+r)/2;
if(check(mid,a,b,n))
r=mid;
else
l=mid;
}
cout<<r<<"\n";
}
Ropes
Code#include<bits/stdc++.h>
using namespace std;
#define int long long
bool balt(vector<int>&v,int k,double x)
{
if(x==0)
{
return true;
}
int cnter=0;
for(int i=0;i<v.size();i++)
{
cnter+=v[i]/x;
}
return cnter>=k;
}
signed main()
{
int n,k;
cin>>n>>k;
vector<int>v(n);
for(auto &i:v)
{
cin>>i;
}
double l=0,r=1e8,mid;
cout<<setprecision(10);
int lp=100;
while(lp--)
{
mid=(l+r)/2;
if(balt(v,k,mid))
{
l=mid;
}
else
{
r=mid;
}
}
cout<<l<<endl;
}
Very Easy Task
Code#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, x, y, t = 0, copies = 0;
cin>>n>>x>>y;
if(x < y)
{
t += x;
}
else
{
t += y;
}
copies = 1;
int l = 0, r = 2e9, ans, mid;
while(l <= r)
{
mid = (l+r)/2;
int T = mid;
int d1 = T/x, d2 = T/y;
int tot = copies + d1 + d2;
if(tot >= n)
{
ans = T;
r = mid-1;
}
else
{
l = mid+1;
}
}
cout<<t+ans<<"\n";
}
Children Holiday
Code#include<bits/stdc++.h>
using namespace std;
#define int int64_t
int m,n;
vector<int>t(1001),z(1001),y(1001);
bool possible(int T){
int cur=m;
for (int i = 0; i < n; ++i)
{
cur-=T / (t[i]*z[i] + y[i] ) * z[i] + min(T % (t[i]*z[i] + y[i] )/t[i],z[i]);
}
return cur<=0;
}
signed main()
{
cin>>m>>n;
for(int i=0;i<n;i++)
{
int a,b,c;
cin>>a>>b>>c;
t[i]=a;
z[i]=b;
y[i]=c;
}
int l=-1,r=1e9;
while(r-l>1)
{
int mid=l+(r-l)/2;
if(possible(mid))
{
r=mid;
}
else
{
l=mid;
}
}
cout<<r<<endl;
int cur=0;
for(int i=0;i<n;i++)
{
if(cur>=m)
{
cout<<0<<" ";
continue;
}
int x=r/(t[i]*z[i]+y[i])*z[i]+min((r%(t[i]*z[i]+y[i]))/t[i],z[i]);
if(x>m-cur){
cout<<m-cur<<" ";
cur+=x;
continue;
}
cur+=x;
cout<<x<<" ";
}
}
Equation
Code#include<bits/stdc++.h>
using namespace std;
bool balt(double x,double c)
{
return (x*x+sqrt(x))>=c;
}
int main()
{
double c;
cin>>c;
double l=0,r=1;
while(!balt(r,c))
{
r*=2;
}
int cnt=0;
while(cnt<100)
{
double mid=(l+r)/2;
if(balt(mid,c))
{
r=mid;
}
else
{
l=mid;
}
cnt++;
}
cout<<setprecision(20)<<r<<endl;
}
String Game
Code#include<bits/stdc++.h>
using namespace std;
bool balt(string a,string b)
{
int n=b.size(),m=a.size();
int i=0,j=0;
while(i<n&&j<m)
{
if(b[i]==a[j])
{
i++;
j++;
}
else
{
i++;
}
}
return j>=m;
}
int main()
{
string s1,s2,s;
cin>>s1>>s2;
s=s1;
int n=s1.size(),m=s2.size();
vector<int>arr(n);
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int l=0,r=n,mid,ans=0;
while(l<=r)
{
mid=(l+r)/2;
s=s1;
for(int i=0;i<mid;i++)
{
s[arr[i]-1]='-';
}
string t="";
for(int i=0;i<n;i++)
{
if(s[i]!='-')
{
t+=s[i];
}
}
if(balt(s2,t))
{
ans=mid;
l=mid+1;
}
else
{
r=mid-1;
}
}
cout<<ans<<endl;
}
Student Councils
Code~~~~~
~~~~~#include<bits/stdc++.h>
define int long long
define double long double
using namespace std; const int N = 2e5 + 7; int a[N]; bool check(int mid, int n, int k) { int councils = 0; for(int i = 1; i <= n; i++) councils += min(a[i], mid); return councils >= mid * k; } main() {
int k,n; cin >> k >> n; for(int i = 1; i <= n; i++) cin >> a[i]; int l = 0; int r = 25e9; while(l < r) { int mid = (l + r + 1) / 2; if(check(mid, n, k)) l = mid; else r = mid — 1; } cout << l << "\n"; }
Hamburgers
Code#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll re[3],hv[3],pr[3],amount;
bool check(long long x){
long long need=0;
for(int i=0;i<3;i++)
need+=max(re[i]*x-hv[i],0ll)*pr[i];
return need<=amount;
}
long long bin(){
long long l=0,h=2e12,md,ans=0;
while(l<=h){
md=(l+h)/2;
if(check(md))
l=md+1,ans=md;
else h=md-1;
}
return ans;
}
int main()
{
string s;
cin>>s;
for(int i=0;i<s.size();i++)
{
re[0]+=(s[i]=='B');
re[1]+=(s[i]=='S');
re[2]+=s[i]=='C';
}
for(int i=0;i<3;i++)
cin>>hv[i];
for(int i=0;i<3;i++)
cin>>pr[i];
cin>>amount;
cout<<bin()<<endl;
}
step 3:
Get together
Code#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
double n;
cin>>n;
vector<int>v(n),arr(n);
for(int i=0;i<n;i++)
{
cin>>arr[i]>>v[i];
}
long double l=-1e9,r=1e9,ans=1e9,mid;
for(int i=1;i<=200;i++)
{
mid=(l+r)/2;
long double a=mid,a2=mid+1e-6;
long double t=0,t2=0;
for(int i=0;i<n;i++)
{
t=max(t,abs(arr[i]-a)/v[i]);
}
for(int i=0;i<n;i++)
{
t2=max(t2,abs(arr[i]-a2)/v[i]);
}
if(t>t2)
{
ans=min(ans,t2);
l=mid;
}
else
{
ans=min(ans,t);
r=mid;
}
}
cout<<fixed<<setprecision(10)<<ans<<endl;
}
Splitting an Array
Code#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int n,k;
cin>>n>>k;
int arr[n],mx=0,tot=0;
for(int i=0;i<n;i++)
{
cin>>arr[i];
mx=max(mx,arr[i]);
tot+=arr[i];
}
int l=mx,r=tot,ans=0,mid;
while(l<=r)
{
mid = (l+r)/2;
int s= mid;
int segments=0,sum=0,mx=0;
bool balt = true;
for(int i=0;i<n;i++)
{
if(max(mx,sum+arr[i])<=s)
{
sum+=arr[i];
mx=max(mx,sum);
}
else
{
if(arr[i]>s)
{
balt=false;
break;
}
segments++;
sum=arr[i];
mx=arr[i];
}
}
if(sum>0)
{
if(mx>s)
{
balt=false;
break;
}
segments++;
}
if(segments>k)
{
balt=false;
}
if(balt)
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
cout<<ans<<endl;
}
Cows in Stalls
Code#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int n,k;
cin>>n>>k;
vector<int>v(n);
for(int i=0;i<n;i++)
{
cin>>v[i];
}
long long l=0,r=1e9,ans=0,mid;
while(l<=r)
{
mid=(l+r)/2;
int cows=1,i=0;
while(i<n)
{
int index=lower_bound(v.begin()+i+1,v.end(),v[i]+mid)-v.begin();
if(index>i&&index<n)
{
i=index;
cows++;
}
else
{
break;
}
}
if(cows>=k)
{
ans=mid;
l=mid+1;
}
else
{
r=mid-1;
}
}
cout<<ans<<endl;
}
Minimum maximum on the Path
Code#include<bits/stdc++.h>
#define int long long
#define double long double
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 2e5 + 7;
vector<pair<int,int>>vec[N],vec2[N];
int dis[N];
void bfs(int m)
{
queue<int>q; q.push(1);
dis[1] = 1;
while(!q.empty()) {
int x = q.front(); q.pop();
for(auto it: vec[x]) {
if(it.second > m) continue;
if(dis[it.first] == 1e9) {
dis[it.first] = dis[x] + 1;
q.push(it.first);
}
}
}
}
bool check(int m, int n, int d)
{
for(int i = 1; i <= n; i++)
dis[i] = 1e9;
bfs(m);
return dis[n] - 1 <= d;
}
main()
{
int n,m,d; cin >> n >> m >> d;
for(int i = 1; i <= m; i++) {
int u,v,c; cin >> u >> v >> c;
vec[u].push_back({v, c});
vec2[v].push_back({u, c});
}
if(!check(1e9, n, d)) {
cout << -1 << "\n";
return 0;
}
int l = 0; int r = 1e9;
while(l < r) {
int mid = (l + r) / 2;
if(check(mid, n, d))
r = mid;
else
l = mid + 1;
}
check(l, n, d);
vector<int>v; v.push_back(n);
int x = n;
while(x != 1) {
for(auto it: vec2[x]) {
if(it.second > l) continue;
if(dis[it.first] == dis[x] - 1) {
v.push_back(it.first);
x = it.first;
break;
}
}
}
cout << v.size() - 1 << "\n";
while(!v.empty()) {
cout << v.back() << " ";
v.pop_back();
}
}
step 4:
Maximum Average Segment
Code#include<bits/stdc++.h>
#define int long long
#define double long double
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 2e5 + 7;
double a[N],b[N],pre[N];
pair<double,int>p[N];
bool check(double x, int d, int n)
{
for(int i = 1; i <= n; i++)
b[i] = a[i] - x;
for(int i = 1; i <= n; i++)
pre[i] = pre[i - 1] + b[i];
p[0].first = 0; p[0].second = 0;
for(int i = 1; i <= n; i++) {
p[i] = p[i - 1];
if(pre[i] < p[i - 1].first) {
p[i].first = pre[i];
p[i].second = i;
}
}
for(int i = d; i <= n; i++) {
int x = i - d;
if(p[x].first <= pre[i])
return 1;
}
return 0;
}
main()
{
int n,d; cin >> n >> d;
for(int i = 1; i <= n; i++)
cin >> a[i];
double l = 0, r = 100;
for(int i = 1; i <= 100; i++) {
double mid = (l + r) / 2;
if(check(mid, d, n))
l = mid;
else
r = mid;
}
//cout << l << "\n";
check(l, d, n);
int a,b;
for(int i = d; i <= n; i++) {
int x = i - d;
if(p[x].first <= pre[i]) {
a = p[x].second + 1;
b = i;
break;
}
}
cout << a << " " << b;
}
Minimum Average Path
Code#include<bits/stdc++.h>
#define int long long
#define double long double
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 2e5 + 7;
double dis[N]; int in[N],par[N];
vector<pair<int,double>>vec[N];
double calculate_distance(int n, double avg)
{
for(int i = 1; i <= n; i++)
in[i] = 0;
for(int i = 1; i <= n; i++) {
dis[i] = 1e18;
for(auto it: vec[i])
in[it.first]++;
}
queue<int>q;
for(int i = 1; i <= n; i++) {
if(!in[i])
q.push(i);
}
dis[1] = 0;
while(!q.empty()) {
int x = q.front(); q.pop();
for(auto it: vec[x]) {
double new_dis = dis[x] + it.second - avg;
if(new_dis < dis[it.first]) {
dis[it.first] = new_dis;
par[it.first] = x;
}
in[it.first]--;
if(!in[it.first])
q.push(it.first);
}
}
return dis[n];
}
bool check(double x, int n) {return calculate_distance(n, x) <= 0;}
main()
{
int n,m; cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u,v; double c;
cin >> u >> v >> c;
vec[u].push_back({v, c});
}
double l = 0; double r = 100;
for(int i = 1; i <= 100; i++) {
double mid = (l + r) / 2;
if(check(mid, n))
r = mid;
else
l = mid;
}
check(l, n);
vector<int>path;
int node = n;
while(node != 0) {
path.push_back(node);
node = par[node];
}
cout << path.size() - 1 << "\n";
while(!path.empty()) {
cout << path.back() << " ";
path.pop_back();
}
}
Pair Selection
Code#include<bits/stdc++.h>
#define int long long
#define double long double
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 2e5 + 7;
double a[N],b[N],c[N];
bool check(double x, int n, int k)
{
for(int i = 1; i <= n; i++)
c[i] = a[i] / x - b[i];
sort(c + 1, c + n + 1);
double sum = 0;
for(int i = n; i >= n - k + 1; i--)
sum += c[i];
return sum >= 0;
}
main()
{
int n,k; cin >> n >> k;
for(int i = 1; i <= n; i++)
cin >> a[i] >> b[i];
double l = 0, r = 1e10;
for(int i = 1; i <= 100; i++) {
double mid = (l + r) / 2;
if(check(mid, n, k))
l = mid;
else
r = mid;
}
cout << fixed << setprecision(10) << l << "\n";
}
step 5:
K-th Number in the Union of Segments
Code#include<bits/stdc++.h>
#define int long long
#define double long double
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 2e5 + 7;
pair<int,int>p[N];
bool check(int mid, int k, int n)
{
int num = 0;
for(int i = 1; i <= n; i++)
num += max(0LL, min(p[i].second, mid) - p[i].first + 1);
return num >= k;
}
main()
{
int n,k; cin >> n >> k;
k++; // to use 1-based indexing
for(int i = 1; i <= n; i++)
cin >> p[i].first >> p[i].second;
int l = -2e9; int r = 2e9;
while(l < r) {
int mid = l + (r - l) / 2; // to deal with negative values
if(check(mid, k, n))
r = mid;
else
l = mid + 1;
}
cout << l << "\n";
}
Multiplication Table
Code#include<bits/stdc++.h>
#define int long long
#define double long double
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 2e5 + 7;
pair<int,int>p[N];
bool check(int mid, int k, int n)
{
int num = 0;
for(int i = 1; i <= n; i++)
num += min(mid / i, n);
return num >= k;
}
main()
{
int n,k; cin >> n >> k;
int l = 1; int r = n * n;
while(l < r) {
int mid = (l + r) / 2;
if(check(mid, k, n))
r = mid;
else
l = mid + 1;
}
cout << l << "\n";
}
K-th Sum
Code#include<bits/stdc++.h>
#define int long long
#define double long double
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 2e5 + 7;
int a[N],b[N];
bool check(int mid, int k, int n)
{
int num = 0;
for(int i = 1; i <= n; i++) {
int x = mid - a[i];
if(x < b[1]) continue; // no elements less than x in the array
int l = 1; int r = n;
while(l < r) {
int m = (l + r + 1) / 2;
if(b[m] > x)
r = m - 1;
else
l = m;
}
num += l;
}
return num >= k;
}
main()
{
int n,k; cin >> n >> k;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++)
cin >> b[i];
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
int l = 1; int r = a[n] + b[n];
while(l < r) {
int mid = (l + r) / 2;
if(check(mid, k, n))
r = mid;
else
l = mid + 1;
}
cout << l << "\n";
}
that all need to learn binary search and I hope you have benefited from this information thanks for all please support me by put like to encourage me