Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 9 Jan, 2021

Search In Rotated Sorted Array

Easy
Asked in companies
GoogleAmazonSiemens

Problem statement

You have been given a sorted array/list 'arr' consisting of ‘n’ elements. You are also given an integer ‘k’.


Now the array is rotated at some pivot point unknown to you.


For example, if 'arr' = [ 1, 3, 5, 7, 8], then after rotating 'arr' at index 3, the array will be 'arr' = [7, 8, 1, 3, 5].


Now, your task is to find the index at which ‘k’ is present in 'arr'.


Note :
1. If ‘k’ is not present in 'arr', then print -1.
2. There are no duplicate elements present in 'arr'. 
3. 'arr' can be rotated only in the right direction.


Example:
Input: 'arr' = [12, 15, 18, 2, 4] , 'k' = 2

Output: 3

Explanation:
If 'arr' = [12, 15, 18, 2, 4] and 'k' = 2, then the position at which 'k' is present in the array is 3 (0-indexed).


Input Format
In the first line, two single-space separated integers ‘n’ and ‘k’, respectively.
The second line, ‘n’ single space-separated integers, denotes the array/list 'arr' elements.


Output Format :
The only line contains the index at which 'k' is present in 'arr'.


Note:
You do not need to print anything; it has already been handled. Just implement the given function.

Approaches

01 Approach

Naively traverse the array and find if ‘k’ is present in ‘arr’ or not. If ‘k’ is present in ‘arr’ return its index else return -1.