Binary Search on Unsorted array

Yes, it's true that binary search can work on the unsorted arrays. Previously we saw that how binary search work on the sorted array as well as have discussed how we can apply binary search on the answer itself.

Let's discuss some problems,

Problem 1:
Search in Rotated Sorted Array - Leetcode, Medium

The Problem statement is very easy to understand, We have given an array some elements are sorted in ascending order, and after that, some elements are sorted in descending order, which means the whole array is unsorted, isn't it?

So we have to find the index of the given target value and there is no duplicate value in the given array.

For solving this problem we have to consider a few cases.

First,

Our target value can take place from L to M.

Second,

Our target value can take place from M to R.

Third,
Somewhere between L to R.

How can we handle these cases?
If our mid-value(a[M]) is greater than the right(a[R]) value then it's possible to target value can exist on the left side.
If the mid is less than the left side it's possible to target value can take place on the right side, otherwise, the target value can take place somewhere between left to right.

Simple Code


Problem 2:

Search in Rotated Sorted Array II - Leetcode, Medium

This Problem is the same as before, but the difference is here duplicates value can exist. We can use the same approach as before, we just need to handle an extra case, we have to ignore duplicates element.

We can do this by using these two line only.

           while (low < high and a[low] == a[low + 1]) {

                low++;

            }

            while (low < high and a[high] == a[high - 1]) {

                high--;

            }

Simple full code

Problem 3:
Find Minimum in Rotated Sorted Array - Leetcode, Medium

Just we have to consider one case here, if right side is greater than middle value, simply we will move to left side.
Simple code:

    int findMin(vector<int>& a) {

        int l = 0, h = (int)a.size() - 1;

        while(l < h){

            int m = (l+h)>>1;

            if(a[h] < a[m]){

                l = m+1;

            }

            else h = m;

        }

        return a[l];

    }


Problem 4:
Find Minimum in Rotated Sorted Array II - Leetcode, Hard

Same as before, but here the array may contain duplicates values.
Simple Code