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 an **integer array**, `nums`, which is **guaranteed** to be a **bitonic** array and a target value. It will return the index if the target is found. If not, it will return `-1`.

**Constraints:**  

- $3 \leq nums.length \leq 10^5$

- $1 \leq nums[i], target \leq 10^8$

- A given array always contains a bitonic point.

- Array `nums` always contain distinct elements.
  
**Example 1:**  
```
Input: [3, 9, 10, 20, 17, 5, 1], 20    
Output: 3
```
**Example 1:**
```
Input: [5, 6, 7, 8, 9, 10, 3, 2, 1], 30    
Output: -1
```

## Intuition
- Use the `findBitonicPoint` function from the previous lesson to find the index of a bitonic point. Then, we will know that all of the elements on the left hand of the bitonic point are arranged in ascending order and all those on the right hand are sorted in descending order. 
- Run the binary search algorithm for the ascending and descending parts, separately.

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

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

-   If $nums[right] == target$, we will return right.
            
-   Return $-1$.


# Problem statement

Suppose we are given an **integer array**, `nums`, which is **guaranteed** to be a **bitonic** array and a target value. It will return the index if the target is found. If not, it will return `-1`.

**Constraints:**  

- $3 \leq nums.length \leq 10^5$

- $1 \leq nums[i], target \leq 10^8$

- A given array always contains a bitonic point.

- Array `nums` always contain distinct elements.
  
**Example 1:**  
```
Input: [3, 9, 10, 20, 17, 5, 1], 20    
Output: 3
```
**Example 1:**
```
Input: [5, 6, 7, 8, 9, 10, 3, 2, 1], 30    
Output: -1
```

# Intuition
- Use the `findBitonicPoint` function from the previous lesson to find the index of a bitonic point. Then, we will know that all of the elements on the left hand of the bitonic point are arranged in ascending order and all those on the right hand are sorted in descending order. 
- Run the binary search algorithm for the ascending and descending parts, separately.

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

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

-   If $nums[right] == target$, we will return right.
            
-   Return $-1$.

Let's try to conduct a binary search of a bitonic array. 

Difficulty Level: Medium

__default

Element in Bitonic Array

Problem statement

Intuition

Algorithm for the BS in the ascending array