ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Given an array sorted in ascending order and is rotated at some pivot, given a target value to search, if found in the array return its index

prodevelopertutorial August 8, 2018

Problem explanation:

Initial Sorted array:
[0,1,2,4,5,6,7]
After rotation it becomes [4,5,6,7,0,1,2].
Target = 0
Index = 4 [as array index starts from 0]

This problem can be solved in 2 ways:

  1. Linear Search
  2. Modified Binary search

 

  1. Linear search:

In this solution, we search the element one by one and return the index. But come on, we shall give the interviewer the 2nd solution.

  1. Modified Binary search

We can solve this by using a modified binary search.

In Binary search, we divide the sorted array into 2 parts. And change the lower index and higher index according to the mid element.

The same solution cannot be applied here, because the array is not sorted. But we know that in a divided array there is always a half that is sorted. Hence we need to find whether the number is in the sorted part or in the rotating part.

We use the below code to achieve the same:

int binary_search_modified(vector<int>& array, int target) 
{
    int low = 0;
    int high = array.size()-1;

    while (low <= high) 
    {
        int mid = ( high-low )/2 + low;
        if (array[mid] == target)
            return mid;

        if (array[mid] < array[high]) 
        {
            if ( array[mid] < target && target <= array[high])
                low = mid + 1;
            else
                high = mid - 1;
        } 
        else 
        {
            if(array[low] <= target && target < array[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
    }
    return -1;
}

Let us understand with an example

 

Input: 
4, 5, 6, 7, 0, 1, 2

Target = 0

Pass 1:
    low = 0
    high = 6

    while(0 <= 6) true
        mid = (6-0) / 2 + 0
            = 3
        if array[3] == target ? false

        if(array[3] < array[6]) => (7 < 2) ? false
            else case
                if(array[0] <= target && target < array[3]) => (4 <= 0 && 0< 7) false
                    else case
                        low = mid + 1 => 3 + 1 >4

Pass 2:
    low = 4
    high = 6
    while (4 <= 6) true
        mid = (6 - 4)/2 + 4 = 5

    if(array[5] == target) ? false

    if(array[5] < array [6]) => (1 < 2 ) true
        if(array[5] < target) && (target <= array[6]) => (1<0 && 0<=2) false
            high = mid -1 => 5 - 1 = 4
Pass 3:
    low = 4
    high = 4

    while(4 <= 4)
        mid = (high - low)/ 2 +low => 4

    if array[4] == target => true
        return 4	

Solution in C++

/*
* File     : search_in_sorted_array.cpp
* Purpose  : Search the target element in a sored array, but reversed at an index
*/
#include<iostream>
#include<vector>
using namespace std;

int binary_search_modified(vector<int>& array, int target) 
{
    int low = 0;
    int high = array.size()-1;

    while (low <= high) 
    {
        int mid = ( high-low )/2 + low;
        if (array[mid] == target)
            return mid;

        if (array[mid] < array[high]) 
        {
            if ( array[mid] < target && target <= array[high])
                low = mid + 1;
            else
                high = mid - 1;
        } 
        else 
        {
            if(array[low] <= target && target < array[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
    }
    return -1;
}

int main()
{

    vector<int> array;

    array.push_back(4);
    array.push_back(5);
    array.push_back(6);
    array.push_back(7);
    array.push_back(0);
    array.push_back(1);
    array.push_back(2);

    int target = 0;


    for (int i = 0; i < array.size(); i++)
    {
        cout <<array[i] << " ";
    }
    cout<<endl;


    int index = binary_search_modified (array, target);
    
    if (index)
    {
        cout<<"The target = "<<target <<" found at index = "<< index<<endl;
    }
    else
    {
        cout<<"Target not found"<<endl;
    }

}

Output:

4 5 6 7 0 1 2
The target = 0 found at index = 4

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters

 

Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io