6. Searching

Binary search variants

0 of 5 activities0%

Reading 1

First true / last false

Open

Lower bound: first index with a[i] >= t. Upper bound: first index with a[i] > t.

Search on answer: binary search the answer space when mid can be checked with a predicate (e.g., minimum capacity).

Predicate must be monotonic.

// lower_bound style
while(lo<hi){
  int mid=lo+(hi-lo)/2;
  if(a[mid]>=t) hi=mid;
  else lo=mid+1;
}

Check 2

Open

Search-on-answer needs the feasibility check to be

Fill in 3

Open

Try it 4

Open

First >= 4.

main.cpp

Loading editor…

Program input (stdin)

Output will appear here.

Assignment 5

Open

Read n, sorted ascending array, t. Print how many elements are strictly < t.

main.cpp

Loading editor…