8 Find an Element in a Rotated Sorted Array

preview_player
Показать описание
FIND AN ELEMENT IN A ROTATED SORTED ARRAY:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:

PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
Рекомендации по теме
Комментарии
Автор

class Solution {
public:

int BinarySearch(vector<int>& nums, int target, int start, int end) {
int l=start, r=end;
while(l<=r){
int mid = (l+r)/2;
if(nums[mid] == target){
return mid;
}
else if(nums[mid] > target){
r = mid-1;
}
else{
l = mid+1;
}
}
return -1;
}

int findMin(vector<int>& nums)
{
int n = nums.size();
int start = 0, end = n-1;
if(nums[start] < nums[end])
{
return 0;
}
while(start <= end)
{
int mid = start + (end - start)/2;
int next = (mid+1)%n;
int prev = (mid + n - 1)%n;
if(nums[mid] <= nums[next] && nums[mid] <= nums[prev])
{
return mid;
}
if(nums[mid] <= nums[end])
{
end = mid - 1;
}
else if(nums[start] <= nums[mid])
{
start = mid + 1;
}
}
return -1;
}

int search(vector<int>& nums, int target)
{
int n = nums.size();
int min_index = findMin(nums);
int a1 = BinarySearch(nums, target, 0, min_index - 1);
int a2 = BinarySearch(nums, target, min_index, n-1);
if(a1 == -1)
return a2;
else
return a1;
}
};



sarthakasthana
Автор

its so satisfying to watch him scribble on the paper idk, the conceps clearity and all is great, but yall have to agree its extremly satisfying to watch him write on the paper

raghavkaul-nmbe
Автор

In the last step, rather than calling BS on both the sub-arrays, we can check if the element we want to search for is greater than first element of the array, if yes then we search it in the first sub-array and if the element is less than the last element of the array, we search it in the second sub-array. If both the conditions are false, we return -1.

rajasjoshi
Автор

Great explaination. Just add this condition for already sorted array.

if (arr[0] <= arr[arr.length-1] ) {
Binary Search in whole array
}

syno.nymous
Автор

I request everyone must practice code on platforms, many corner and other cases remain untouched sometimes.

deepakgurjar
Автор

for my refernce
int lo = 0;
int hi = nums.size()-1;

while(lo<=hi)
{
int mid = lo+(hi-lo)/2;

if(nums[mid] == target)
return mid;
// we are finding sorted side, b/c in sorted side we can find that whether our target element is available within the sorted range in O(1) time, if available then shift high to mid-1; and if not available within the range-> lo = mid+1 and then again mid is calculated and then once again we find the sorted part of that sub array and then we search for target element in the range, if found hi = mid-1; if not found in sorted range -> lo then again repeat the process
else if(nums[mid]>= nums[lo]) // means left side is sorted
{
if(target >= nums[lo] && target < nums[mid])
hi = mid-1;
else
lo = mid+1;
}
// if left side is not sorted then obviously right side will be sorted, b/c in rotated array one half is always sorted
else
{
// checking if target is available within the sorted range, if yes then discard the left search space, else if target not in range at right side then move hi to mid-1 and discard the right search space and then again calculate mid and then find sorted sub part of that sub array
if(target <= nums[hi] && target > nums[mid])
lo = mid+1;
else
hi = mid-1;
}
}

return -1;

spiral
Автор

So, there can be another solution which is also easy to understand, and a bit less lengthier than the one explained by him.
Lemme first give the intuition of this solution,
for any given index or point in a rotated sorted array, there exists one sorted sub-array and one unsorted sub-array, for eg:-
arr[]: 8 10 12 16 18 3 5 6
at index =2, val=12, 8 10 is the sorted one
12 16 18 3 5 6 is the unsorted one
at index =6, val=5, 8 10 12 16 18 3 is the unsorted one
5 6 is the sorted one

So, what we can do is we can just normally find the middle element for a rotated sorted array, and from this middle point one part will be sorted, one will be unsorted,
-> So, how can i check if my 1st sub-array is sorted, just check if first element is less than middle element or not, if it is, then the 1st part is sorted, now knowing this part is sorted, how can I check if my target element exists in this part or not.
just check that the target element is greater than the first element and less than the middle element, if this is true, then there's a possibility that the target element lies here, just have to perform normal binary search here.. If it doesn't lie here, then we're sure enough that we don't have to traverse this sorted part (first=mid+1), we can skip this whole part(just like normal binary search), and traverse in the unsorted part.

->secondly, how can I check if my second part is sorted or not, just check, is your middle element less than the last element or not. If it's true, your second part is sorted.
Now, how can I check if my target lies in this 2nd part(which is now the sorted one), just check if target is greater than middle and less than last or not. If it's true, then the target can lie here, just have to perform normal binary search here.
If it's not true, eliminate this whole sorted array, (by doing last=mid-1), and traverse in the unsorted part.

So, basically, I'm just a picking a point(obviously the middle element), and dividing my array into two parts, one is sorted, and the other one is unsorted, checking if my target lies in the sorted part by applying conditions, if it's there, performing normal binary search, and if it's not there then just skipping this whole sorted part, and moving towards the unsorted part.
In the unsorted part, again I'm dividing the array into two parts and doing the same.

Here's the code:-

int search(int A[], int l, int h, int key){

int n=sizeof(A);
if(n==1 && key==A[0])
return 0;

else if(n==1 && key!=A[0])
return -1;

else
{
int mid;
while(l<=h)
{
mid=l+ (h-l)/2;

if(A[mid]==key)
{
return mid;
break;
}
else if(A[l]<=A[mid])
{
if(A[l]<=key && key<=A[mid])
h=mid-1;
else
l=mid+1;
}
else
{
if(A[mid]<=key && key<=A[h])
l=mid+1;
else
h=mid-1;
}
}
return -1;
}
}

kirtikhohal
Автор

you can do it in just 1 binary search at the end. if the key <= last element then search in right half else left half

charan
Автор

Optimised solution-> complexity log(n):
int search(vector<int>& nums, int target) {
int lo = 0, hi = int(nums.size()) - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
lo = mid + 1;
else
hi = mid;
}
return lo == hi && nums[lo] == target ? lo : -1;
}

gauravkhulway
Автор

number of rotation in clockwise direction =len(array)-index of minimum element

riteshkumarpandey
Автор

sorry to say but the moving condition is incorrect (moves towards unsorted) taking the video example first sorted array will be 11 to 18 second will be 2 to 5 and then 6 but we have to find the minimum element

this is correct condition
while (s <= e) {
int mid = s + (e - s) / 2;

if (nums[mid] == target) {
return mid;
} else if (nums[s] <= nums[mid]) {
if (nums[s] <= target && target <= nums[mid]) {
e = mid - 1;
} else {
s = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[e]) {
s = mid + 1;
} else {
e = mid - 1;
}
}
}

return -1;

onechance
Автор

Solution Leetcode accepted:
class Solution {
public int search(int[] nums, int target) {
int arrayStartIndex = findRotation(nums);
int index= binarySearch(nums, arrayStartIndex, nums.length-1, target);
int index2 = binarySearch(nums, 0, arrayStartIndex-1, target);
return index==-1?index2:index;
}

public int findRotation(int [] arr){
int N = arr.length;
int start = 0, end = N-1;
while(start<=end){
int mid = start + (end - start)/2;
int prev = (mid - 1 + N)%N;
int next = (mid + 1)%N;
if(arr[mid]<=arr[prev] && arr[mid]<=arr[next])
return mid;
else if(arr[mid]>=arr[0])
start = mid+1;
else
end = mid-1;
}
return 0;
}

public int binarySearch(int [] arr, int start, int end, int target){

while(start<=end){
int mid = start + (end - start)/2;
if(arr[mid] == target)
return mid;
else if(arr[mid]>=target)
end = mid-1;
else
start = mid + 1;
}
return -1;
}
}

vipulgupta
Автор

leetcode soln: class Solution {
public:

int BinarySearch(vector<int>& nums, int target, int s, int e) {
while(s<=e){
int mid = s+(e-s)/2;
if(nums[mid] == target)
return mid;
else if(target < nums[mid])
e = mid-1;
else
s = mid+1;
}
return -1;
}

int findMin(vector<int>& nums)
{
int n = nums.size(), start = 0, end = n-1;
if(nums[start] < nums[end]) //if sorted and unrotated//
return 0;

while(start <= end){
int mid = start + (end - start)/2;
int next = (mid+1)%n;
int prev = (mid + n - 1)%n;
if(nums[mid] <= nums[next] && nums[mid] <= nums[prev]) //if mid element is min Elem//
return mid; //1. then both neighbors must be smaller than it//
if(nums[mid] <= nums[n-1])
end = mid - 1; //2. if mid is not min Elem, move towards unsorted as it has min Elem//
else if(nums[0] <= nums[mid])
start = mid + 1;
}
return -1;
}

int search(vector<int>& a, int target)
{
int n = a.size();
if(a[0]<a[n-1]) //since sorted not rotated//
return BinarySearch(a, target, 0, n-1);

int min_index = findMin(a);

if(target == a[min_index])
return min_index;
if(target>=a[0])
return BinarySearch(a, target, 0, min_index - 1);

return BinarySearch(a, target, min_index+1, n-1);
}

};

aartibhatnagar
Автор

similar simplified approach:
public int search(int[] a, int k) {
int n=a.length;
int l=0;
int h=n-1;
while(l<=h){
int m=l+((h-l)/2);
if(a[m]==k){
return m;
}
if(a[m]>=a[l]){
if(a[m]>=k&&a[l]<=k)
{
h=m-1;
}
else
l=m+1;
}
else {
if(k>=a[m]&& k<=a[h])
l=m+1;
else{
h=m-1;;
}
}
}
return -1;
}

harshmishra
Автор

Solution 1: We know how to apply binary search to sorted array. So find pivot and apply BS in both sorted array. We know array from pivot to end is sorted so instead of applying on both we can opitimize it by checking condition beforehand. Still complexity is 2Log(n) as we are traversing it two times. Check solution 2.
class Solution {
public:
int getPivotIndex(vector<int>& arr) {
int beg = 0, end = arr.size()-1;
while(beg <= end) {
int mid = beg + (end - beg) / 2;
if (mid >=1 && arr[mid] < arr[mid-1]) {
return mid;
} else if (arr[mid] >= arr[0]) {
beg = mid + 1;
} else {
end = mid - 1;
}
}
return 0;
}

int bs(vector<int>& arr, int beg, int end, int target) {
while(beg <= end) {
int mid = beg + (end - beg) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] <= target) {
beg = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}

int search(vector<int>& arr, int target) {
int pivot = getPivotIndex(arr);
return target <= arr.back() ? bs(arr, pivot, arr.size() - 1, target):
bs(arr, 0, pivot-1, target);
}
};

Solution 2: Our aim is to compare the target with the mid and eliminate the incorrect half. We know there is a pivot in either the left half or the right one. If pivot is in left of mid, this means at least from mid + 1 to right the array is sorted. So we can compare whether our target lies in this part. If yes eliminate left part and search in this space else move to left part. Similarly if pivot is on right of mid, the part from beg to mid will be sorted and we can do the same comparison with target and eliminate the incorrect part. This is done in a single traversal so it is better O(log(n))

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

sarthakbhatia
Автор

all test cases passed code :

int n =arr.size();

int takeindex=-1;
int start =0;
int end=n-1;
while(start<=end)
{
int mid = (start + end)/2;
int prev=(mid-1+n)%n;
int next =(mid+1)%n;
if(arr[mid]<=arr[prev] && arr[mid]<=arr[next])
{takeindex = mid;
break;}
else if(arr[mid]<=arr[end]){
end=mid-1;
}
else
{
start=mid+1;
}
}

if(arr[takeindex]==target)
return takeindex;

start =takeindex;
end=n-1;
int one =-1;
while(start<=end)
{
int mid = (start + end)/2;

if(arr[mid]==target)
{ one = mid;
break;}
else if(arr[mid]>=target){
end=mid-1;
}
else
{
start=mid+1;
}
}
if(one!=-1)
return one;

start =0;
end=takeindex-1;
int two = -1;
while(start<=end)
{
int mid = (start + end)/2;

if(arr[mid]==target)
{two = mid;
break;}
else if(arr[mid]>=target){
end=mid-1;
}
else
{
start=mid+1;
}
}

if(two!=-1)
return two;

return -1;

growmore
Автор

class Solution {
int findKRotation(int arr[], int n) {
// code here
if(n==1) return 0;

int start = 0;
int end = n-1;


// Index of smallest element is our answer here

while(start<=end){
// If all elements of array are already sorted
if(arr[start]<=arr[end])
return start;

// Calculate mid
int mid = start +(end - start)/2;

int next = (mid +1)%n;// if mid is at last position
int prev = (mid +n-1)%n; // if mid is at first position
// If we found smallest element of array, store it's index

if((arr[mid]<=arr[next])&& (arr[mid]<= arr[prev])){
return mid;
// If left part of array is sorted, It means
// smallest element present in right part
}
// If left part of array is sorted, It means
// smallest element present in right part
else if (arr[start]<= arr[mid]){
start = mid +1;
}
// If right part of array is sorted, It means
// smallest element present in left part
else {
end = mid -1;

}

}
return 0;

}

}

adityamaurya
Автор

one more condition:--> if we land up on a new array which is completely sorted we need to treat it as ordinary Binary Seach problem.. where-> start < mid && mid < end

Saurabh-febg
Автор

Very good, simple and clear explanation. Thank you.

prakashkchauhannn
Автор

simple c++ code:

#include<iostream>
using namespace std;

int binary_search(int arr[ ], int s, int e, int data){
while(s<=e){
int mid=s+(e-s)/2;

if(arr[mid]==data)
return mid;

else if(data>arr[mid])
s=mid+1;

else if(data<arr[mid]){
e=mid-1;
}
}
return -1;
}

int findMinEle(int arr[ ], int n)
{
int s = 0, e = n - 1;
if(arr[s]<=arr[e])
return 0; /*returns 0 if array is already sorted*/
while (s <= e) {

// if first element is mid or
// last element is mid
// then simply use modulo so it
// never goes out of bound.
int mid = s + (e - s) / 2;
int prev = (mid - 1 + n) % n;
int next = (mid + 1) % n;

if (arr[mid] <= arr[prev] && arr[mid] <= arr[next])
return mid;
else if (arr[mid] <= arr[e])
e = mid - 1;
else if (arr[mid] >= arr[s])
s = mid + 1;
}
return -1;
}

int searchInRotatedSorted(int arr[ ], int n, int index, int data){
int left_search = binary_search(arr, 0, index-1, data);
int right_search = binary_search(arr, index, n-1, data);
if(left_search ==-1 && right_search ==-1){
return -1;
}
else if(left_search != -1){
return left_search;
}
else{
return right_search;
}
/* or you can use this comparision also
if(left_search == -1)
return right_search;
else
return left_search;
*/
}

int main( ){
int arr[ ] = {11, 12, 15, 18, 2, 5, 6, 8};
int size = sizeof(arr)/sizeof(arr[0]);
int min_ele_index = findMinEle(arr, size);
int data;
cout<<"Enter data to be searched in rotated sorted array: ";
cin>>data;
int ans = searchInRotatedSorted(arr, size, min_ele_index, data);
if(ans==-1){
cout<<data<<" is not present in rotated sorted array";
}
else{
cout<<data<<" found at index: "<<ans;
}
return 0;

}

amanbalhara