Grokking Binary Search for Coding Interviews_468 x 60 copy.png

Binary Search (BS) is, arguably, the most popular question in coding interviews. Even when you see that a problem can be solved with BS, it can be tricky to handle all of the indexes and base cases in the solution. What if there was an approach that could work for all BS problems? 
This course was designed from scratch with this one goal in mind. We'll explore one technique that can handle any BS problem. The practice problems in this course were carefully chosen to cover the most frequently asked BS questions in coding interviews. At the end of this course, you will feel confident to handle BS questions during phone or on-site interviews, as well as with all of the follow-ups about its time and space complexity.

Binary Search for Coding Interviews

# Problem statement

Suppose we are given a **sorted array** of distinct integers, `nums`, which are sorted in ascending order. We will return the **smallest index** `i`, which satisfies `nums[i] == i`. If no such `i` exists, we will return `-1`.

**Constraints:**

- $1 \leq nums.length \leq 10^3$
- $-10^3 \leq nums[i] \leq 10^3$

**Example 1: General case**
```
Input: [-10,-5,0,3,7]    
Output: 3    
```
**Explanation:** For the given array, `nums[0] = -10`, `nums[1] = -5`, `nums[2] = 0`, `nums[3] = 3`, the output is `3`.

**Example 2: The answer is at the beginning of the array**
```
Input: [0,2,5,8,17]    
Output: 0    
```
**Explanation:** `nums[0] = 0`. Thus the output is `0`.

**Example 3: The answer is missing**
```
Input: [-10,-5,3,4,7,9]    
Output: -1    
```
**Explanation:** There is no such `i` that `nums[i] = i`. Thus the output is `-1`.

# Intuition
This problem is similar to the first challenge that we solved in the previous lesson. But, in the case of this problem, there is a greater range of integers and the index we are looking for is absent. An index of an element is our target here.
 

# Algorithm
    
-   Set the $left$ boundary to $0$, and the $right$ boundary to the size of nums.
    
-   While $left + 1 < right$:
    
    -   Take $mid = \frac{(left + right)}{2}$ as a guess. Compare $nums[mid]$ with $target$:
        
        -   If $nums[mid] == mid$ and $left < nums[left]$, the job will be done and we will return the index.
            
        -   Else, if $nums[mid] < mid$, then we will move the left boundary $left = mid$.
            
        -   Otherwise, if $nums[mid] > mid$, then we will move the right boundary $right = mid$.

-   If $nums[left] == left$, then we will return $left$.

-   If $right <$ size of $nums$ and $nums[right] == right$, then we will return $right$
            
-   Return $-1$

Let's check another problem with a sorted input array.

Difficulty Level: Easy

__default

First Element Equals its Index

Problem statement