DSA - Binary Search

studied byStudied by 1 person
1.0(1)
learn
LearnA personalized and smart learning plan
exam
Practice TestTake a test on your terms and definitions
spaced repetition
Spaced RepetitionScientifically backed study method
heart puzzle
Matching GameHow quick can you match all your cards?
flashcards
FlashcardsStudy terms and definitions

1 / 23

encourage image

There's no tags or description

Looks like no one added any tags here yet for you.

24 Terms

1

Recoggnize a Binary Search Problem

  1. Sorted List / monotonic

  2. minimize Maxima

  3. maximize Minima

  4. Optimization - if you have solved a problem and they ask you to optimize it then Binary Search is one of the widely used approach.

  5. N = 10^5 and values are 10^9 / 10^8

New cards
2

Binary Search AZ Way

convert the array so that it’s a series of 0s and 1s and then just return the first occurrence of 1.

A = [0, 0 ,0, 0, 0 , 1, 1, 1, 1]

We need to find the first occurrence of 1.

New cards
3

if l and r are given, how do you calculate mid?

l + (r-l)/2 because (l+r)/2 can overflow

New cards
4

Lowerbound (arr, n),

  1. will return the number greater or equal to n

  2. or will return num of elements < x, by subtracting what we got from 1 by start of array

example arr = [1, 3, 5, 5, 7, 7, 9]

lb(arr, 5) = 5 or iterator pointing to index 2

now if we subtract 2- 0 = num of elements smaller than 5

New cards
5

upperbound(arr, n)

  1. will return the number STRICTLY greater to n

  2. or will return num of elements <= x, by subtracting what we got from 1 by start of array

example arr = [1, 3, 5, 5, 7, 7, 9]

ub(arr, 5) = 7 or iterator pointing to index 4

now if we subtract 4- 0 = num of elements smaller or equal to 5

ub(arr, 9) = arr.end

New cards
6

template for binary search problems

int check(vector<int> &a, int m)
{
if (a[m] < a[0])
return 1;
return 0;
}

void solve(vector<int> &a)
{
int l = 0, r = a.size() - 1, ans = 0;
while (l <= r)
{
int m = l + (r - l) / 2;
if (check(a, m) == 0)
{
l = m + 1;
}
else
{
ans = m;
r = m - 1;
}
}
cout << ans << '\n';
}

Important answer is what we need to return when we won’t find the number in the array

Check is the main function which converts our array into 0 0 0 1 1 1 kind of array

New cards
7

for lower bound (number greater than or equal to x)

int check(vector<int> &a, int m, int x)
{
if (a[mid] <= x) mid] < x) //compare mid with the given element
return 1;
return 0;
}

eg this logic will convert

[1, 3, 5, 5, 7, 7, 9] and x = 5

into 0 0 1 1 1 1 1, so any element greater or equal to 5 will be converted to 1, rest all to 0, so answer will be 5 or index(2)

New cards
8

C++: binary_search

In C++, the Standard Template Library (STL) provides binary_search in the <algorithm> header.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> arr = {1, 3, 5, 7, 9};
if (binary_search(arr.begin(), arr.end(), 5)) {
cout << "5 is present\n";
} else {
cout << "5 is not present\n";
}
return 0;
}
  • Returns true if the element is found, otherwise false.

  • The range [begin, end) must be sorted.

New cards
9

C++'s STL also provides lower_bound() and upper_bound() in the <algorithm> header.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
vector<int> arr = {1, 3, 5, 7, 9};

auto lb = lower_bound(arr.begin(), arr.end(), 5);
auto ub = upper_bound(arr.begin(), arr.end(), 5);

cout << "Lower bound of 5: " << (lb - arr.begin()) << "\n"; // Output: 2
cout << "Upper bound of 5: " << (ub - arr.begin()) << "\n"; // Output: 3

return 0;
}
  • lower_bound() returns an iterator to the first element greater than or equal to the given value.

  • upper_bound() returns an iterator to the first element greater than the given value.

  • Both require the range [begin, end) to be sorted.

New cards
10

Python: bisect.bisect_left() and bisect.bisect_right()

Python provides the bisect module for binary search operations.

import bisect

arr = [1, 3, 5, 7, 9]
index = bisect.bisect_left(arr, 5)
if index < len(arr) and arr[index] == 5:
print("5 is present at index", index)
else:
print("5 is not present")
  • bisect_left() returns the position where the value should be inserted to maintain sorted order. « lowerbound

  • bisect_right() gives the position after the last occurrence of the value. « upperbound

  • The array must be sorted.

New cards
11
New cards
12

for upper bound (number Strictly greater than x)

int check(vector<int> &a, int m, int x)
{
if (a[mid] < x) //compare mid with the given element
return 1;
return 0;
}

eg this logic will convert

[1, 3, 5, 5, 7, 7, 9] and x = 5

into 0 0 0 0 1 1 1, so any element greater or equal to 5 will be converted to 1, rest all to 0, so answer will be 7 or index(4)

New cards
13

Rotated Sorted Array

Check Function

int check(vector<int> &a, int mid, int x)
{
if (a[mid] < a[0]) //compare mid with first element
return 1;
return 0;
}

eg this logic will convert

3 4 5 1 2

into 0 0 0 1 1

we see that at the point of rotation, that is 1, is less than the first element 3, and so are all elements after 1, eg 2 in this case

New cards
14

For Bitonic array

Check Function

int check(vector<int> &a, int m, int x)
{
if (a[mid] > a[mid + 1]) //compare mid with the next element
return 1;
return 0;
}

eg this logic will convert

1 2 5 3 2 1

into 0 0 0 1 1 1

we see that at the point of rotation, that is 1, is less than the first element 3, and so are all elements after 1, eg 2 in this case

New cards
15

find one element which is single in an array of duplicate numbers

here we see that before the number the pairs are in even, odd position and after the number they change to odd, even position, so our check function will be

int check(vector<int> &A, int mid) {
if (mid %2 == 0) {
if (A[mid] == A[mid + 1])
return 0;
else return 1;
} else {
if (A[mid] == A[mid -1]) return 0;
return 1;
}
return 0;
}

so we need to convert

1 1 7 2 2 3 3 → 0 0 1 1 1 1 1

you see before the single digit 7, the pairs are in even odd position that is 0 and 1 and after 7 they shift a position by 1 so 2 2 are in 3 4 positions (odd, even) that;s what we do in the check function.

If mid is at even position then it’s next should be it’s duplicate, if the mid is at odd position then it’s prev should be it’s pair

New cards
16

Binary search types of problems

  1. BS On Answer

    • Atomic Items contribution

    • Sweep Coverage

    • 2D Variations

  2. BS on Every Start - Can be done by 2 pointers

New cards
17

Binary search Time Complexity

Time complexity of check function * TC of check space

New cards
18

Painters partition problem

The Painter’s Partition Problem (or similar problems) fundamentally boils down to a pattern of partitioning an array into K subarrays in a way that minimizes the maximum sum of any subarray.

Time complexity of check function TC of check space = O(log(sum of array) *n

the search space will be from 0 to sum of all elements.We will see if for a given time

New cards
19

Binary search on answers problems so far, book allocation, painters problem, aggressive cows, this last one, place k points in given n points and the last one Given an array of integers A and an integer B, find and return the maximum value K such that there is no subarray in A of size K with the sum of elements greater than B, square root Can you summarize in a table what kind of problem is is maximizing the min or min the max, start, end values, what is the check function doing and what would be the transformation array 0 0 0 1 1 1 or 1 1 1 1 0 0 0

Problem

Goal

Search Range Start (Low)

Search Range End (High)

Check Function

Transformed Array Pattern

Book Allocation

Minimize the maximum pages allocated to a student

1

Sum of all pages

Determines if current max pages per student is feasible (can allocate to all students within limit)

[0 0 0 1 1 1]

Painter’s Partition

Minimize the maximum time needed for painters

1

Sum of all painting times

Determines if painters can paint all sections within a given time constraint

[0 0 0 1 1 1]

Aggressive Cows

Maximize the minimum distance between cows

1

Maximum distance between the two furthest stalls

Checks if cows can be placed with at least the given distance between each other

[1 1 1 0 0 0]

Place K Points Between N Points

Minimize the maximum separation between consecutive points

1

Maximum initial gap between consecutive points in sorted list

Determines if we can achieve a maximum separation by adding up to K points

[0 0 0 1 1 1]

Array Subarray Sum Constraint

Maximize the minimum subarray size with sum <= B

1

Length of array

N

N

N

Checks if a given subarray size has all subarrays with sum <= B

[1 1 1 0 0 0]

New cards
20

Binary search - Aggressive cows - Check function

Approach:

The check function is a key part of solving this problem. Its purpose is to determine if it’s possible to place C cows in the stalls such that the minimum distance between any two cows is at least a given distance d.

  • Place the First Cow: Start by placing the first cow in the first stall (position arr[0]). This ensures we leave the largest possible space for the remaining cows.

  • Track Remaining Cows:

    • We initialize a count for the remaining cows (cows = c - 1) since we’ve already placed the first cow.

    • We also keep track of the position of the last placed cow (prev = arr[0]).

  • Place the Rest of the Cows:

    • Iterate through the stalls, starting from the second one.

    • For each stall, check if it’s at least d distance away from the last placed cow.

    • If it is, place a cow there and update prev to the current stall’s position.

    • Decrease the cows count after placing a cow.

  • Check if All Cows Are Placed:

    • If all cows are placed successfully (i.e., cows == 0), return true, meaning it’s possible to place the cows with at least d distance between them.

  • If Not All Cows Are Placed:

    • If the loop finishes and we haven’t placed all cows, return false, meaning it’s not possible to place the cows with that distance.

Complexity:

  • Time Complexity: O(N) We are iterating through the array once.

  • Space Complexity: O(1) We have not used extra space.

bool check(int arr[], int d, int n, int c)
{
//Complete this function to check if c cows can be arranged into n stalls with d distance
int cows = c;
cows--;
int prev = arr[0];

for(int i=1; i<n; i++) {
if(arr[i] - prev >= d) {
cows--;
prev=arr[i];
}
if (cows==0) return true;
}
return false;
}

New cards
21

Binary search on 2D Matrix - mapping 1D index to 2D matrix

Mapping a 1D Index to a 2D Matrix

Given a 2D matrix A with n rows and m columns, we can treat the matrix as a flattened 1D array of size n * m. The index mid in this 1D array needs to be converted back to the corresponding row and column indices in the 2D matrix.

Calculation of x and y

  1. Row Index (x):

    • The row index x is calculated as mid / m.

    • This works because dividing the 1D index by the number of columns (m) gives the number of complete rows that fit into the index.

    • For example, if mid is 7 and m is 3, then x = 7 / 3 = 2. This means the 7th element is in the 2nd row (0-based index).

  2. Column Index (y):

    • The column index y is calculated as mid % m.

    • This works because taking the modulus of the 1D index by the number of columns (m) gives the position within the row.

    • For example, if mid is 7 and m is 3, then y = 7 % 3 = 1. This means the 7th element is in the 1st column (0-based index) of the 2nd row.

Example

Consider a 2D matrix:

A = [

  [1, 3, 5],

  [7, 9, 11],

  [13, 15, 17]

]

  • This matrix has n = 3 rows and m = 3 columns.

  • If mid = 4, then:

    • x = mid / m = 4 / 3 = 1 (integer division)

    • y = mid % m = 4 % 3 = 1

  • So, A[x][y] corresponds to A[1][1], which is 9.

New cards
22

Binary search on 2D Matrix - Code

Code Context

In the provided code:

int Solution::searchMatrix(vector<vector<int>> &A, int B) {
int n = A.size();
if (n == 0) return 0;
int m = A[0].size();
int l = 0, r = m * n - 1;

while (l <= r) {
int mid = l + (r - l) / 2;
int x = mid / m;
int y = mid % m;
if (A[x][y] == B) return 1;
if (A[x][y] < B) l = mid + 1;
else r = mid - 1;
}
return 0;
}
  • mid is the current index in the 1D representation of the matrix.

  • x = mid / m calculates the row index.

  • y = mid % m calculates the column index.

  • A[x][y] accesses the element in the 2D matrix at the calculated row and column.

This approach allows the binary search to be performed on the 2D matrix as if it were a 1D array, ensuring efficient search operations.

New cards
23
New cards
24
New cards

Explore top notes

note Note
studied byStudied by 11 people
1117 days ago
5.0(1)
note Note
studied byStudied by 19 people
836 days ago
5.0(1)
note Note
studied byStudied by 469 people
761 days ago
5.0(1)
note Note
studied byStudied by 6 people
799 days ago
5.0(1)
note Note
studied byStudied by 27 people
720 days ago
4.0(2)
note Note
studied byStudied by 36 people
834 days ago
4.5(2)
note Note
studied byStudied by 8 people
540 days ago
5.0(1)
note Note
studied byStudied by 214 people
672 days ago
5.0(2)

Explore top flashcards

flashcards Flashcard (20)
studied byStudied by 9 people
756 days ago
5.0(1)
flashcards Flashcard (74)
studied byStudied by 52 people
737 days ago
4.8(8)
flashcards Flashcard (108)
studied byStudied by 9 people
25 days ago
5.0(2)
flashcards Flashcard (169)
studied byStudied by 20 people
64 days ago
5.0(3)
flashcards Flashcard (39)
studied byStudied by 45 people
811 days ago
5.0(1)
flashcards Flashcard (20)
studied byStudied by 3 people
679 days ago
5.0(1)
flashcards Flashcard (38)
studied byStudied by 92 people
394 days ago
5.0(1)
flashcards Flashcard (33)
studied byStudied by 6 people
756 days ago
5.0(1)
robot