# Binary Search

### **Pre-condition**

The array you are searching should be sorted (or more generally, the function should be monotonic)

### **Aim**

Given a sorted array, find an element in the array (and return its index). Return -1 if the element is not in the array.

### **Invariant**

If you are searching for key in an array (and key actually exists in the array),then `A[begin] <= key <= A[end]`is true at every step of the procedure.

### **Code**

```java
public int BSearch(A, key, n) {
	begin = 0;
	end = n - 1;
	while begin < end {
		mid = begin + (end - begin)/2 // to avoid overflow error, we don't use (begin+end)/2
		if key <= A[mid] {
			end = mid;
		} else {
			begin = mid + 1;
		}
	return (A[begin] == key) ? begin : - 1
```

### **Running time**

$$O(\log n)$$

At each stage, the array size to be searched splits in half. So, the running time reccurence relation is $$T(n)= T(\dfrac{n}{2}) +O(1)$$. The solution to this recurrence relation can easily be determined to be $$O(\log n)$$.

Binary search is often a part of much larger solution to a complicated problem. For example, you can binary search over the range of possible answers if you have a lower bound and an upper bound, and you have some monotonic property.

### Questions

<mark style="background-color:red;">**Random number guesser -**</mark> <mark style="background-color:red;"></mark><mark style="background-color:red;">Given that a random number has been chosen between 1 and 1024, guess the number correctly in less than 12 tries. Every time you make a guess, you will know whether your guess was too high or too low.</mark>

Ans: Just apply Binary Search with `begin = 1`and `end = 1024`

<mark style="background-color:red;">**Smallest Indistinguishable Integer -**</mark> <mark style="background-color:red;"></mark><mark style="background-color:red;">Given that there exists a limit beyond which integers cannot be represented effectively in a computer system, your task is to find the smallest number that is indistinguishable from its successor. An integer</mark> $$i$$ <mark style="background-color:red;">is said to be indistinguishable if</mark> $$i == i + 1$$ <mark style="background-color:red;">returns true.</mark>

Ans: Consider the function `boolean isDistinguishable(int i)`.Observe that the function here is monotonic. In other words, once the function crosses a certain threshold (that we need to find), it will always return indistinguishable, whereas it will always return distinguishable for values before the threshold. So, first try to the largest power of 2 (by multiplying by 2 at each iteration) that can be represented effectively, i.e, find $$j$$ such that $$2^j$$ is distinguishable but $$2^{j+1}$$ is not. Then apply Binary Search to find the exact integer between $$\[2^j, 2^{j+1}]$$.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs2040s.devanshshah.dev/algorithms/binary-search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.