# Binary Search

suggest change# Introduction

Binary Search is a Divide and Conquer search algorithm. It uses `O(log n)`

time to find the location of an element in a search space where `n`

is the size of the search space.

Binary Search works by halving the search space at each iteration after comparing the target value to the middle value of the search space.

To use Binary Search, the search space must be ordered (sorted) in some way. Duplicate entries (ones that compare as equal according to the comparison function) cannot be distinguished, though they donâ€™t violate the Binary Search property.

Conventionally, we use less than (<) as the comparison function. If a < b, it will return true. if a is not less than b and b is not less than a, a and b are equal.

# Example Question

You are an economist, a pretty bad one though. You are given the task of finding the equilibrium price (that is, the price where supply = demand) for rice.

*Remember the higher a price is set, the larger the supply and the lesser the demand*

As your company is very efficient at calculating market forces, you can instantly get the supply and demand in units of rice when the price of rice is set at a certain price `p`

.

Your boss wants the equilibrium price ASAP, but tells you that the equilibrium price can be a positive integer that is at most `10^17`

and there is guaranteed to be exactly 1 positive integer solution in the range. So get going with your job before you lose it!

You are allowed to call functions `getSupply(k)`

and `getDemand(k)`

, which will do exactly what is stated in the problem.

# Example Explanation

Here our search space is from `1`

to `10^17`

. Thus a linear search is infeasible.

However, notice that as the `k`

goes up, `getSupply(k)`

increases and `getDemand(k)`

decreases. Thus, for any `x > y`

, `getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y)`

. Therefore, this search space is monotonic and we can use Binary Search.

The following psuedocode demonstrates the usage of Binary Search:

high = 100000000000000000 <- Upper bound of search space low = 1 <- Lower bound of search space while high - low > 1 mid = (high + low) / 2 <- Take the middle value supply = getSupply(mid) demand = getDemand(mid) if supply > demand high = mid <- Solution is in lower half of search space else if demand > supply low = mid <- Solution is in upper half of search space else <- supply==demand condition return mid <- Found solution

This algorithm runs in `~O(log 10^17)`

time. This can be generalized to `~O(log S)`

time where S is the size of the search space since at every iteration of the `while`

loop, we halved the search space (*from [low:high] to either [low:mid] or [mid:high]*).

**C Implementation of Binary Search with Recursion**

int binsearch(int a[], int x, int low, int high) { int mid; if (low > high) return -1; mid = (low + high) / 2; if (x == a[mid]) { return (mid); } else if (x < a[mid]) { binsearch(a, x, low, mid - 1); } else { binsearch(a, x, mid + 1, high); } }