Algorithms and Data Structures

Binary Search

Video preview
Imagine we have written down the heights of all the buildings in the world in increasing order. So, the first element is the world's shortest building, and the last one is the tallest one. We play a game in which given a query number that represents the height of a building, you should reply with the position (the index) of that building in the list. In case there is no building with the requested height, you reply with -1.
A naive approach would be to run a for loop to process each and every element in the array and check against the query. In the worst-case scenario, this will do n operations for each query (in case the number of elements in the array is n).
h = [...]                # Heights of all the buildings in increasing order
q = int(input())         # The query height

for i, height in enumerate(h):
    if height == q:      # In case we find the element
        print(i)         # Print the index
		    break            # And stop
else:                    # In case we didn't find a building with height q (else = nobreak)
    print(-1)            # Print -1 to indicate that we didn't find it
Yet, realizing that the list is sorted in increasing order, you start to notice that we perform a ton of redundant operations. Instead of looping over the list from the beginning to the very end, we could’ve probably jumped over some redundant operations to arrive at the correct index quicker.
As we have the whole array sorted in increasing order, a more optimal way of approaching this problem would be by looking at the middle element in the array. If that element is smaller than q, we can throw away the whole left half of the array and concentrate on the right one only. If that element is larger than q, we can throw away the whole right part, and concentrate on the left one. The process of looking at the middle element and throwing away the redundant half until finding the right element is essentially the Binary Search algorithm.
h = [...]                # Heights of all the buildings in increasing order
q = int(input())         # The query height

l, r = 0, len(h)         # The answer always lies between [l; r). Note that r is exclusive
while r - l > 1:         # There is at least one element in between to consider
    mid = (l + r) // 2   # Take the middle index
    if h[mid] > q:       # h[mid] > q => throw away the right half
        r = mid
    else:                # h[mid] <= q => throw away the left half
        l = mid

# We should arrive at h[l] being the query element
print(l if h[l] == q else -1)
Imagine we have an array of building heights h = [20, 22, 23, 23, 34, 49, 52, 55, 58] and we would like to know the index of a building with height 49.
With this algorithm, we would perform several iterations:
  1. mid = (0 + 9) // 2 = 4 ⇒ h[4] = 34 ≤ 49 ⇒ we throw away the left part.
  1. mid = (4 + 9) // 2 = 6 ⇒ h[6] = 52 > 49 ⇒ we throw away the right part.
  1. mid = (4 + 6) // 2 = 5 ⇒ h[5] = 49 ≤ 49 ⇒ we throw away the left part.
  1. l = 5, r = 6 ⇒ r - l == 1 ⇒ the while loop ends and we print 5 as h[5] = 49.
 
This small example might not seem like a lot of optimization but imagine if we had 10 billion buildings. In case of looping over each and every element, we would perform 10 billion iterations in the worst-case scenario. Yet, in the case of splitting the array in half every time and throwing away the redundant parts, this is a huge performance gain. Let’s see how many iterations it would take us to converge to an answer if we split 10 billion elements on every iteration:
Spoiler: it’s only 32 iterations instead of 10 billion
  1. 10,000,000,000 / 2 = 5,000,000,000
  1. 5,000,000,000 / 2 = 2,500,000,000
  1. 1250000000 / 2 = 625000000
  1. 625000000 / 2 = 312500000
  1. 312500000 / 2 = 156250000
  1. 156250000 / 2 = 78125000
  1. 78125000 / 2 = 39062500
  1. 39062500 / 2 = 19531250
  1. 19531250 / 2 = 9765625
  1. 9765625 / 2 = 4882812
  1. 4882812 / 2 = 2441406
  1. 2441406 / 2 = 1220703
  1. 1220703 / 2 = 610351
  1. 610351 / 2 = 305175
  1. 305175 / 2 = 152587
  1. 152587 / 2 = 76293
  1. 76293 / 2 = 38146
  1. 38146 / 2 = 19073
  1. 19073 / 2 = 9536
  1. 9536 / 2 = 4768
  1. 4768 / 2 = 2384
  1. 2384 / 2 = 1192
  1. 1192 / 2 = 596
  1. 596 / 2 = 298
  1. 298 / 2 = 149
  1. 149 / 2 = 74
  1. 74 / 2 = 37
  1. 37 / 2 = 18
  1. 18 / 2 = 9
  1. 9 / 2 = 4
  1. 4 / 2 = 2
  1. 2 / 2 = 1
So, imagine there is an algorithm that does a linear search by going through each and every item in a 10-billion-item collection, and checking each element takes 1 second. That algorithm will take 317 years to complete. While doing a binary search would take only 32 seconds!
This is the difference between doing operations and operations.

Challenge

Given n GPAs from 1 to 4 (1 is the lowest grade and 4 is the perfect one), and several thresholds, you are asked to tell how many people would pass to the next grade if one should be at the threshold and above to pass.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ ) the number of students.
The next line contains n floating point numbers representing the GPAs of students in increasing order (1 ≤ ≤ 4).
The third line contains a single integer q (1 ≤ q ≤ ) the number of thresholds to consider.
The last line of the input contains q floating point numbers representing the minimum thresholds to pass to the next grade (1 ≤ ≤ 4).

Output

The program should print q lines. Line i should represent the number of students that would pass to the next grade given the threshold .

Examples

Input
Output
10 1.1 1.2 1.4 1.7 2 3 3.3 3.5 3.8 3.8 5 3.7 3.8 1 1.5 2
2 2 10 7 6
 

Constraints

Time limit: 6 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue