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 an array that was **sorted** in ascending order is __rotated__. For example, the array `nums = [0,1,2,4,5,6,7]` might become:

-   `[4,5,6,7,0,1,2]`, if it is rotated `4` times.
-   `[0,1,2,4,5,6,7]`, if it is rotated `7` times.

Notice that _rotating_ an array `[nums[0], nums[1], nums[2], ..., nums[n-1]]` `1` time results in the array `[nums[n-1], nums[0], nums[1], nums[2], ..., nums[n-2]]`.

Suppose we are given a **sorted rotated array** `nums`, and an **integer** `target`. If `target` is found in the array, we will return its index. Otherwise, we will return `-1`.

**Constraints:**

-   1 \leq nums.length \leq 5000
-   -10^4 \leq nums[i] \leq 10^4
-   All of the values of `nums` are  **unique**.
-  `nums` is guaranteed to be rotated at some pivot.
-   -10^4 \leq target \leq 10^4

**Example 1:**
```
Input: [4,5,6,7,0,1,2], 0    
Output: 4
```
**Example 2:**
```
Input: [4,5,6,7,0,1,2], 3    
Output: -1
```
**Example 3:**
```
Input: [1], 0    
Output: -1
```

# Problem statement

Suppose an array that was **sorted** in ascending order is __rotated__. For example, the array `nums = [0,1,2,4,5,6,7]` might become:

-   `[4,5,6,7,0,1,2]`, if it is rotated `4` times.
-   `[0,1,2,4,5,6,7]`, if it is rotated `7` times.

Notice that _rotating_ an array `[nums[0], nums[1], nums[2], ..., nums[n-1]]` `1` time results in the array `[nums[n-1], nums[0], nums[1], nums[2], ..., nums[n-2]]`.

Suppose we are given a **sorted rotated array** `nums`, and an **integer** `target`. If `target` is found in the array, we will return its index. Otherwise, we will return `-1`.

**Constraints:**

-   1 \leq nums.length \leq 5000
-   -10^4 \leq nums[i] \leq 10^4
-   All of the values of `nums` are  **unique**.
-  `nums` is guaranteed to be rotated at some pivot.
-   -10^4 \leq target \leq 10^4

**Example 1:**
```
Input: [4,5,6,7,0,1,2], 0    
Output: 4
```
**Example 2:**
```
Input: [4,5,6,7,0,1,2], 3    
Output: -1
```
**Example 3:**
```
Input: [1], 0    
Output: -1
```

Let's modify the problem with a rotated sorted array and solve it. 

Difficulty Level: Medium

__default

Element in Rotated Sorted Array

Problem statement