HEADSTART
Programming and Algorithms
Group
INTRO TO BINARY SEARCH AND
TWO POINTERS METHOD
Binary
Search
Searching
We are trying to find something. It can be anything, an
index, an element, a value, a node or even the answer
itself!
So,
Let’s do some searching !!
Where is
54?
Where is
56?
Intuition for
Binary Search
Binary search is an algorithm to quickly search something
in a monotonous collection.
It is based on the observation that once we compare a
value to the required value, we can determine on
which side of this value does our required value
lie. So, we can skip checking that side for our
value.
So, how do we actually apply this observation ?
Active Region is
Implementation
generally
marked by two
variables, start
and end.
Consider a sorted array containing 54.
You wanna find its position.
We’ll maintain an active region where it can be.
Initially, that’s the whole array.
Compare the middle element (mid) of active region with 54.
If it’s greater than 54, change end to mid.
If it’s less than or equal to 54, change start to mid+1.
Repeat till your active region has only one element
(start==end),
Congratulations! You have found 54 or not.
Pseudocode
low = 0, high = n - 1;
while (low <= high)
{
mid = (low + high) / 2;
if(a[mid]==54){
return mid; Can you guess the
}
if (a[mid] < 54) complexity?
{
low = mid + 1;
}
else{
high = mid;
}
}
return -1;
Complexity Calculation
So, first of all let’s imagine an active region in our array
(At the beginning the entire array would be the active
region ).
Then, we check the middle element of this region. Upon
seeing it, either we would have found what we were
searching for or we can determine on which side of this
region does it lie ? Hence in one step we effectively half
the size of our active region.
So, the number of steps to obtain an active region of
size 1 is about log(n).
How Fast Is It?
Find 37!
Binary Search on Answer
Sometimes, it is easy for us to check our answer and we
can also search it binarily ( ie answers after a value are
all true and before a value are all false or vice versa).
This technique is quite useful and can help solve
questions very quickly.
00000000000000001111111111111
Question Time
Question
Find the smallest integral n such that n²+n>1e18
(Try to do it with binary search)
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n = 1e9 ;
long long l = 0, r = n + 1;
while (l < r){
long long mid = (l + r) / 2; Code for
long long temp = mid * mid + mid;
if (temp <= n){
Finding first 1.
l = mid + 1;
}
else{
r = mid;
}
}
cout << r << endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n = 1e9 ;
long long l = 0, r = n + 1;
while (l < r){
long long mid = (l + r + 1) / 2;
Code for
long long temp = mid * mid + mid; finding
if (temp <= n){
l = mid; last 0.
}
else{
r = mid - 1;
}
}
cout << l << endl;
return 0;
}
Implementing
Interesting, we can see that whenever, searching
anything in a monotonous collection, our binary search
problem can be either be broken down into largest value
satisfying or smallest value not satisfying
Let’s try a question
https://codeforces.com/contest/1873/problem/E
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
ll n, x;
cin >> n >> x;
ll height[n];
for (int i = 0; i < n; i++){
cin >> height[i];
}
ll l = 0, r = 1e10;
while (l < r){
ll mid = (l + r) / 2;
ll count = 0;
for (int i = 0; i < n; i++){
if (mid > height[i]){
count += mid - height[i];
}
}
if (count <= x){
l = mid + 1;
}
else{
r = mid;
}
}
cout << l - 1 << endl;
}
}
https://cses.fi/problemset/task/1620
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ll n, k;
cin >> n >> k;
ll times[n];
for (int i = 0; i < n; i++){
cin >> times[i];
}
ll l = 0, r = 1e18 + 1;
while (l < r){
ll mid = (l + r) / 2;
ll count = 0;
bool chk = 0;
for (int i = 0; i < n; i++){
count += mid / times[i];
if (count > 1000000000){
chk = 1;
break;
}
if (count >= k || chk){
r = mid;
}
else{
l = mid + 1;
}
}
cout << l << endl;
}
Binary Search available in
STL?
Direct Functions available in STL library of C++
so you don’t have to write the implementation.
Lower Bound:
Lower Bound of x returns the index of element
greater than or equal to x in a sorted array or
vector.
Upper Bound:
Upper Bound of x returns the index of element
Example
Consider the array A = [1,2,3,3,4,5,6,8]
Lower Bound of 3 = 2
Upper Bound of 3 = 5
Lower Bound of 9 = 8
Upper Bound of 8 = 8
Lower Bound of 0 = 0
Upper Bound of 0 = 0
Some more Questions
https://codeforces.com/problemset/
problem/474/B
https://codeforces.com/problemset/
problem/1703/F
Two
pointe
r
metho
Introduction
The Two Pointers Method is an important technique that is often used
in competitive programming. It is a broad concept which helps us
deal with a multitude of problems.
As the name suggests, we will be using two pointers to approach the
question in hand. This may be applied whenever:
● Dealing with properties of contiguous subarrays
● Dealing with sorted arrays and searching
● Dealing with specifically two values in a given set
Motivation Problem - !
Given two non-decreasingly sorted arrays A and B of sizes n and m
respectively, merge the two arrays to form a third array C such that it is also
non-decreasingly sorted.
Constraints :
1 ≤ n , m ≤ 5 x 105
-109 ≤ A[i] , B[j] ≤ 109 ∀ 0 ≤ i ≤ n - 1 & 0 ≤ j ≤ m - 1
A = [ 10 , 15 , 231 ]
B = [ 12 , 17 , 211 , 420 ,
2911 ]
} C = [ 10 , 12 , 15 , 17 , 211 , 231 , 420
, 2911 ]
https://codeforces.com/edu/course/2/le
sson/9/1/practice/contest/307092/prob
lem/A
Approach - !
Naive Solution :
Create a new array, consisting of elements from both the
given arrays and sort them. The complexity thus achieved
is O( (n + m) log(n + m) ).
Better Solution :
The main observation is that since both arrays are already sorted, we
need not compare elements of the same array. So we only need
to compare the elements of A with elements of B.
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int a1[n],a2[m];
vector<int>ans;
for (int i=0;i<n;i++)
cin>>a1[i];
for (int i=0;i<m;i++)
cin>>a2[i];
int first = 0,second = 0;
while (first < n && second < m)
{
if (a1[first] < a2[second]){
ans.push_back(a1[first]);
first++;
}
Solution - !
else{
ans.push_back(a2[second]);
second++;
}
}
if (first < n)
{
for (int i=first;i<n;i++)
ans.push_back(a1[i]);
}
else if (second < m)
{
for (int i=second;i<m;i++)
ans.push_back(a2[i]);
}
for (int i=0;i<n+m;i++)
cout<<ans[i]<<' ';
return 0;
}
Motivation Problem - !!
Given an array of 𝑛 integers 𝑎[𝑖]. Let's say that the segment of this array
𝑎[𝑙..𝑟] (1≤𝑙≤𝑟≤𝑛) is good if the sum of elements on this segment is at most
𝑠. Your task is to find the length of longest good segment.
Constraints :
1 ≤ n ≤ 105 , 1 ≤ s ≤ 1018
1 ≤ A[i] ≤ 109 ∀ 0 ≤ i ≤ n - 1
A=[2,6,4,3,6,8,9
] }
Ans = 4
https://codeforces.com/edu/course/2/le
sson/9/2/practice/contest/307093/prob
lem/A
Approach - !!
Naive Solution :
Check for all subarrays, using prefix sum optimisation this
boils down to number of subarrays i.e. O(n^2)
Better Solution :
Use two pointers lol
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,s;
cin>>n>>s;
int arr[n];
for (int i=0;i<n;i++)
cin>>arr[i];
int l=0,r=0;
int ans = 0;
int sum = arr[l];
while (l < n && r < n)
{
if (sum <= s){
ans = max(ans,r-l+1);
Solution - !!
r++;
sum+=arr[r];
}
else{
sum-=arr[l];
l++;
}
}
cout<<ans<<"\n";
return 0;
}
Enough motivation, now time for
questions.
Three sum?
You are given an array of n integers, and your task is to find
three values (at distinct positions) whose sum is x.
•1≤n≤5000
•1≤x,ai≤10^9
Input:
4 10
1 2 5 7
Output:
0 1 3
https://cses.fi/problemset/task/1641/
Solution
@pag_iitr
facebook.com/sdspag
discord.gg/egUQEdt3
