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'.
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.
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).
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.
The only line contains the index at which 'k' is present in 'arr'.
You do not need to print anything; it has already been handled. Just implement the given function.
4 3
8 9 4 5
-1
For the test case, 3 is not present in the array. Hence the output will be -1.
4 3
2 3 5 8
1
Try to do this in O(log(n)).
1 <= n <= 10^5
0 <= k <= 10^9
0 <= arr[i] <= 10^9
Time Limit: 1 second
Naively traverse the array and find if ‘k’ is present or not.
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.
O(N), where N is the length of the array/list.
We are iterating over the array/list ‘arr’ once. Hence, the time complexity is O(N).
O(1), i.e. constant space complexity.
All tags
Sort by
Interview problems
java
import java.util.ArrayList;
public class Solution {
public static int search(ArrayList<Integer> arr, int n, int k) {
// Write your code here.
int low=0,high=n-1;
while(low<=high){
int mid=(low+high)/2;
if(arr.get(mid)==k) return mid;
if(arr.get(low)<=arr.get(mid)){
if(arr.get(low)<=k && k<=arr.get(mid)){
high=mid-1;
}else low=mid+1;
}
else{
if(arr.get(mid)<=k && k<=arr.get(high)){
low=mid+1;
}else high=mid-1;
}
}
return -1;
}
}
Interview problems
java
import java.util.ArrayList;
public class Solution {
public static int search(ArrayList<Integer> arr, int n, int k) {
// Write your code here.
for(int i=0;i<n;i++){
if(arr.get(i)==k){
return i;
}
}
return -1;
}
}
Interview problems
Pivot + Binary + Short Code | c++
int pivot(vector<int>& arr,int n){
int low=0,high=n-1;
int mid = low + (high-low)/2;
while(low<high){
if(arr[mid]>=arr[0])
low = mid+1;
else
high = mid;
mid = low + (high-low)/2;
}
return low;
}
int search(vector<int>& arr, int n, int k){
int low=0,high=n-1;
int mid = pivot(arr,n);
while(low<=high){
if(arr[mid]==k) // pivot pe milgya
return mid;
else if(arr[mid]<k && arr[high]>=k) // 2nd monotonous line
low = mid+1;
else
high = mid-1; // 1st monotonus line
mid = low + (high-low)/2;
}
return -1;
}
Interview problems
Binary search in java
import java.util.ArrayList;
public class Solution {
public static int search(ArrayList<Integer> arr, int n, int k) {
// Write your code here.
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if the element at mid is the target
if (arr.get(mid) == k) {
return mid;
}
// Check if the left half is sorted
if (arr.get(low)<= arr.get(mid)) {
// Check if 'k' is in the range of the left half
if (arr.get(low) <= k && k < arr.get(mid)) {
high = mid - 1; // Search the left half
} else {
low = mid + 1; // Search the right half
}
}
// Otherwise, the right half must be sorted
else {
// Check if 'k' is in the range of the right half
if (arr.get(mid) < k && k <= arr.get(high)) {
low = mid + 1; // Search the right half
} else {
high = mid - 1; // Search the left half
}
}
}
// If we reach here, 'k' is not in the array
return -1;
}
}
Interview problems
C++ Using Binary Search
int search(vector<int>& arr, int n, int k)
{
int low=0, high=n-1;
while(low<=high){
int mid=(low+high)/2;
if (arr[mid]==k) return mid;
// when you not find target in mid so need to find sorted half array either left to mid and Right to mid
//if array is left sorted
if (arr[low]<=arr[mid]){
if(arr[low]<=k && k<=arr[mid]){
high=mid-1;
}
else{
low=mid+1;
}
}
// else right array is sorted
else{
if( arr[mid]<= k && k<=arr[high]){
low=mid+1;
}
else{
high=mid-1;
}
}
}
return -1;
// Write your code here.
// Return the position of K in ARR else return -1.
}
Interview problems
Search in sorted rotated array
int pivotIndex(vector<int> &arr, int n, int k){
int s = 0;
int e = n - 1;
int mid = s + (e - s)/2;
while(s<e){
if(arr[mid] >= arr[0]){
s = mid + 1;
}
else{
e = mid;
}
mid = s + (e - s)/2;
}
return s;// we can also return e;
}
int binarySearch(vector<int>&arr, int start, int end, int k){
int s = start;
int e = end;
int mid = s + (e-s)/2;
while(s <= e){
if(arr[mid] == k){
return mid;
}
else if(arr[mid]<k){
s = mid + 1;
}
else{
e = mid - 1;
}
mid = s + (e-s)/2;
}
return -1;
}
int search(vector<int> &arr, int n, int k) {
// Write your code here.
// Return the position of K in ARR else return -1.
//first we have to find the pivot index which can help to //decide whether we should move in the array to find //the k
int pivot = pivotIndex(arr, n, k);
//this is for line 2
if (arr[pivot] <= k && k <= arr[n - 1]){
return binarySearch(arr, pivot,n-1,k);
}
//this is for line 1
else{
return binarySearch(arr, 0,pivot-1,k);
}
}
Interview problems
Use Binary search for that
int search(vector<int>& arr, int n, int k)
{
int low = 0;
int high = n-1;
//target = k
while(low<=high){
int mid = (low + high)/2;
//If found return mid index
if(arr[mid] == k){
return mid;
}
//if target lies at left half and it is sorted
if(arr[low] <= arr[mid]){
if(arr[low]<=k && arr[mid]>= k){
high = mid-1;
}
//if target is not in left half it is in righthalf
else{
low = mid + 1;
}
}
else{
//if target lies in right half and it is sorted
if(arr[mid]<=k && k <= arr[high]){
low = mid + 1;
}
//if target is in right half
else{
high = mid-1;
}
}
}
return -1;
}
Interview problems
Binary Search 🔥🔥
#include<bits/stdc++.h>
int search(vector<int>& arr, int n, int target)
{
// Write your code here.
// Return the position of K in ARR else return -1.
// Binary Search
int low = 0;
int high = n-1;
while(low <= high){
int mid = low + (high-low)/2;
if(arr[mid] == target) return mid;
// if left half is sorted
if(arr[low] <= arr[mid]){
if(arr[low] <= target && target <= arr[mid]){
// target lie in left half
high = mid-1;
}
else{
// target lie in right half
low = mid+1;
}
}
// if right half is sorted
else{
if(arr[mid] <= target && target <= arr[high]){
// target lie in right half
low = mid+1;
}
else{
// target liew in left half
high = mid-1;
}
}
}
return -1;
}
Interview problems
can anyone tell me why this code exceeds the time
int getpivot(vector<int>& arr,int n){
int s=0;
int e = n-1;
int mid = s+(e-s)/2;
while(s<e){
if (arr[mid] >= arr[0]) {
s = mid + 1;
}else{
e=mid;
}
}
return s;
}
int binarySeach(vector<int>& arr,int s,int e,int k){
int mid = s+(e-s)/2;
while(s<=e){
if(arr[mid]==k){
return mid;
}
if(arr[mid]>k){
e = mid-1;
}else{
s = mid+1;
}
}
return -1;
}
int search(vector<int> &arr, int n, int k) {
int pivot = getpivot(arr,n);
if(k >= arr[pivot]&& k<= arr[n-1]){
return binarySeach(arr,pivot,n-1,k);
}else{
return binarySeach(arr,0,pivot-1,k);
}
}
Interview problems
How to optimize it?
int search(vector<int>& arr, int n, int k)
{
// Write your code here.
// Return the position of K in ARR else return -1.
int s=0;
int e=n-1;
int mid = s+(e-s)/2;
while(s<=e){
if(arr[mid]==k)
return mid;
//if mid is greater than start
if(arr[s]<=arr[mid]){
//if key is between start and mid
if(arr[s]<=k && k < arr[mid]){
e=mid-1;
}
//if key is not between start and mid
else{
s=mid+1;
}
}
else{
//if key is between mid and end
if(arr[mid]<k && k<=arr[e]){
s=mid+1;
}
else{
e=mid-1;
}
}
mid=s+(e-s)/2;
}
return -1;
}
