Binary Search

It is a searching algorithm, which is used to find the specific element in the sorted array. It works on the divide-and-conquer technique, which divides the problem size into two more minor size problems.

Binary search is an approach that is used to solve the problems related to searching. 

For more Details of how Binary search works click here.

Where to apply the Binary search approach.

Whenever We can identify the answer to the problem lies between in range L to R, and there is a monotonic behavior of the answer in the range L to R then, we can think of a Binary search.

Example:

Peak Index in a Mountain Array (Leetcode)

Problem Statement:

You are given an integer mountain array arr of length n where the values increase to a peak element and then decrease. Return the index of the peak element.

Example 1:

Input: arr = [0,1,0]

Output: 1

Solution:

Firstly, we can apply Brute force, as the peak element is the maximum element in the array, we will traverse through the array and keep the track of maximum array.

Code:

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        // index of maximum element
        int maxIndex=0;
        for(int i=1;i<arr.size();i++){
            if(arr[i]>arr[maxIndex]) maxIndex=i;
        }
        return maxIndex;
    }
};

Complexity:

Time Complexity: O(n)

Space Complexity: O(1)

Where,

      n = size of the input array.

Binary Search Approach

To optimize the search, we can apply Binary search.

Why apply binary search

In this problem, array = [0,1,2,3,2,1] is sorted in the range of 0 to peak element in ascending order and from peak to length-1 sorted in descending order. So, we can go for a binary search.

How to apply

Let arr = [0,1,2,3,2,1]

Peak element =3

Favorable condition:

 Arr[mid]>arr[mid-1] && arr[mid] > arr[mid+1]

The pseudocode will be as follows: Initialize variables L = 0 and R = arr.size() - 1. Compute the middle index as mid = L + (R - L) / 2, compared with favorable conditions, update the value of L and R accordingly, and continue the search until the peak element is found.

code:

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int l=0,h=arr.size()-1;
        while(l<=h){
            int mid=l+(h-l)/2;
            if(arr[mid]>arr[mid-1] && arr[mid]>arr[mid+1]) return mid;
            else if(arr[mid-1]<arr[mid]) l=mid+1;
            else h=mid;
        }
        return -1;
    }
};

Complexity:

Time complexity: O(logn)
space complexity: O(1)
where,

     n = size of the input array.