Count Less Than Using Binary Search | Dataford Interview Questions

The Expedia app stores available hotel prices in a sorted integer array. Given the sorted prices and a target price, return how many prices are strictly less than the target.

You must solve the problem using binary search. Duplicate prices should be counted separately, and a price equal to the target is not considered less.

Formal Specification

Implement count_less_than(prices, target).

Input: prices, a nondecreasing list of integers, and target, an integer.
Output: An integer representing the number of elements in prices whose value is strictly less than target.
The input list must not be modified.

Constraints

0 <= len(prices) <= 100,000
-10^9 <= prices[i], target <= 10^9
prices is sorted in nondecreasing order
Duplicate values are allowed

Function Signature

def count_less_than(prices, target):

Your question is Count Less Than Using Binary Search. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem