Search in a rotated sorted array, understanding how to apply binary search in weird conditions🤔 🤨
Tags: javascript, computerscience, career, programming
Published: 2020-04-19 15:43:15

Question: You're given a sorted array but it's rotated around a pivot. You're given a target value to search. If found return the index or return -1. Assume that array doesn't contain duplicates. 

Eg: 
sorted array = [0,1,2,4,5,6,7] 
rotated array = [4,5,6,7,0,1,2] 

If the target is 5, we return 1. 

<h2>Brute Force : O(n)</h2> 
Brute Force approach would be to traverse through the array and return the index. Plain and simple. 

But as you know brute force search on a sorted list is not the best idea : 
<img src = "https://media.giphy.com/media/STwc6NmfG8pNxkO0nH/giphy.gif" /> 

<h2> Binary Search : O(log n) </h2>

A little demo on how Binary Search works : 
<img src = "https://blog.penjee.com/wp-content/uploads/2015/04/binary-and-linear-search-animations.gif" />

We want to modify the binary search algorithm since the given array is rotated at a pivot and is not strictly sorted. 

Let's start with what we have and know how to work on it. 

Since the array is <strong> Rotated Sorted </strong> array, and we know how to perform binary search on a sorted array. SO let's divide the array into two halves and call the left and right.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/7nfo9kh59xxybpwpz45q.png)

Once we get the two sorted arrays, we can perform a binary search on the two sorted arrays and get find the target in O(long). Pretty cool right? 

<strong> BUT </strong> how to find the pivot point where we should divide the array? 
One way is to search for the pivot by going through the list but it would take O(n) time. So we need a different way of searching for that pivot. 

<strong>How about using Binary Search for Pivot? </strong> 
You might now be thinking, "Akhil, you just said that we can't perform Binary Search to find the target but you're using Binary Search for finding the pivot ?? Isn't pivot similar to target?" 

Yes, you're right but notice that while searching for <strong>target</strong>, we're literally blind, but while searching for <strong>pivot</strong>, we know for a fact that <strong> arr[pivot-1] > arr[pivot] < arr[pivot+1] </strong>, and we're going to use this one key property to find that sweet little pivot. 

<strong> Let's search the pivot </strong> 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/73y6erjy4thszgf1z53v.png)

Here we're just converting towards finding that minimum element in the array. 
We face 2 cases : 
1> if arr[mid] > arr[right], it means we're in <strong>right<strong> sorted array, so go towards left to find the pivot element.
2> else it means the array is rotated, so go towards left to find that <strong> right </strong> sorted array. 


Let's code it : 
```javascript 
    let left = 0;
    let right = nums.length-1;
    
    while(left < right){
        let mid = Math.floor((left+right)/2);
        if(nums[mid]>nums[right]){
            left = mid+1;
        }else{
            right = mid;
        }
    }    
```

Now that we've found our pivot, let's work on finding the target. 

So, how to figure out where is our <strong>target</strong> located, is it in the <strong> left subarray </strong> or <strong> right subarray</strong> ? 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/ing141r2t6e15vde5ha2.png)

Let's code this part: 
```javascript
    let pivot = left;
    left = 0;
    right = nums.length-1;
    
    if(nums[pivot]<=target && target <= nums[right]){
        left = pivot;
    }else{
        right = pivot;
    }
```

Now that we know which part our target lies, let's perform binary search on that subarray: 
```javascript
 while(left<=right){
        let mid = Math.floor((left+right)/2);
        if(nums[mid] == target){
            return mid;
        }
        if(nums[mid]<target){
            left = mid+1;
        }else{
            right = mid-1;
        }
    }
    return -1;
```

Now that we have all the bit's and parts, lets put it all together : 
```javascript

var search = function(nums, target) {
    
    if(nums.length == 0 || nums == null) return -1;
    
    let left = 0;
    let right = nums.length-1;
    
    while(left < right){
        let mid = Math.floor((left+right)/2);
        if(nums[mid]>nums[right]){
            left = mid+1;
        }else{
            right = mid;
        }
    }
    
    let pivot = left;
    left = 0;
    right = nums.length-1;
    
    if(nums[pivot]<=target && target <= nums[right]){
        left = pivot;
    }else{
        right = pivot;
    }
    
    while(left<=right){
        let mid = Math.floor((left+right)/2);
        //console.log(mid , nums[mid] , target);
        if(nums[mid] == target){
            return mid;
        }
        if(nums[mid]<target){
            left = mid+1;
        }else{
            right = mid-1;
        }
    }
    return -1;
    
};

```

That's it ! Now you know how to apply and take advantage of binary search in weird conditions. 

Thank's a lot if you've made it till here 🥰, leave comment's down below if you've any doubts or you want me to cover a question. 

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/SearchInRotatedSortedArray.js