9 Searching in a Nearly Sorted Array

SEARCH IN A NEARLY SORTED ARRAY:

Given an array which is sorted, but after sorting some elements are moved to either of the adjacent positions, i.e., arr[i] may be present at arr[i+1] or arr[i-1]. Write an efficient function to search an element in this array. Basically the element arr[i] can only be swapped with either arr[i+1] or arr[i-1].

For example consider the array {2, 3, 10, 4, 40}, 4 is moved to next position and 10 is moved to previous position.

Example :
Input: arr[] = {10, 3, 40, 20, 50, 80, 70}, key = 40
Output: 2
Output is index of 40 in given array

------------------------------------------------------------------------------------------
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.

[bismeetsingh]

I think we can also wrap n-1 and n+1 using modulo.
def binary_search(target):
low=0
high=len(arr) - 1
n=len(arr)
while low <= high :

mid = low + (high - low)//2

if arr[mid]==target:
return mid

previous = (mid-1)%n
next=(mid+1)%n

if arr[previous]==target:
return previous

if arr[next]==target:
return next

if target<arr[mid]:
high=mid-2
else:
low=mid+2
return -1

arr=[10, 3, 40, 20, 50, 80, 70]
ans=binary_search(90)
print(ans)

[rabishaw]

U relate one code to other in very easy way thanks for such a amazing content and playlist

[newman]

Your explanation is very logical and algorithmic .wonderful.

[nikhilmohanty]

C++ code:

int search(vector<int> &arr, int target)
{
int n = arr.size();
int start = 0, end =n-1;

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

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

[sastecoder]

if we make a small sort then apply binary search, then also work fine

int solve(){
vector<int> nums = {5, 10, 30, 20, 40};
int target, n = nums.size();
cin>>target;

int low = 0, high = nums.size()-1;
while(low <= high) {
int mid = low + ((high - low) >> 1);
int next = (mid+1)%n;
int prev = (mid-1+n)%n;

if(nums[mid] == target) return mid;
else if(nums[prev] == target) return prev;
else if(nums[next] == target) return next;
else {
vector<int> mp = {nums[prev], nums[mid], nums[next]};
sort(mp.begin(), mp.end());

if(mp[1] < target) low = mid+1;
else high = mid-1;
}
}
now(low);
now(high);
return -1;
}

[himanshusahu]

good content yaar, best way to learn step by step every topic, please make playlist for linkedlist, tree etc. as well, in the same way. Thanks bro.

[somnathnavale]

Initially 2:45 I was clueless when he say Jo ata hai usse compare Karo I relate with previous problem and able to solve😄😄 thanks Aditya for such wonderful content.

[rabishaw]

Bhyia ur explanation style is amazing
Please make video on recursion and backtracking

[jitendrapradhan]

You deserve our success, hats to you....

[SuperNirajpandey]

Working code:

#include <iostream>
using namespace std;
//searching in a nearly sorted array
int main() {
int a[] = {5, 10, 30, 20, 40};
int n = sizeof(a)/sizeof(a[0]);
int k = 40;
int start = 0;
int end = n-1;

int result = -1;

while(start <= end)
{
int mid = start + ((end-start)/2);

if(k == a[mid])
{
result = mid;
break;
}
if((mid-1) >= start && k == a[mid-1])
{
result = mid-1;
break;
}
if((mid+1) <= end && k == a[mid+1])
{
result = mid+1;
break;
}

if(k <= a[mid-2])
{
end = mid-2;
}
else if(k >= a[mid+2])
{
start = mid+2;
}
}
cout<<result;
return 0;
}

[RajeevCanDev]

HE HAS THE BEST HANDWRITTING THAT COULD EVER EXIST!!

[raviashwin]

bro which topic is coming next as you previously said to upload more videos on may, waiting eagerly for it,

[nitinpraksh]

here is full code :


public static int arr, int k) {

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

[ShubhamGupta-dmij]

Sir, please upload tutorial of segment tree

[kuskargupt]

Other two conditions should be as follows:

else if( arr[mid] < num_to_be_searched )
l = mid+2;
else if( arr[mid] > num_to_be_searched )
r = mid-2;

[cyborg]

C++ implementation for the above problem.

#include <bits/stdc++.h>
using namespace std;

int bs(int arr[], int low, int high, int x)
{
while(low <= high)
{
int mid = low + (high-low)/2;
if(arr[mid] == x)
return mid;
if(mid > low && arr[mid-1] == x)
return mid-1;
if(mid < high && arr[mid+1] == x)
return mid+1;
if(arr[mid] < x)
{
low = mid + 2;
}
if(arr[mid] > x)
high = mid - 2;
}
return -1;
}

int main()
{
int arr[] = {5, 10, 30, 20, 40};
cout << bs(arr, 0, 4, 20);
return 0;
}

[srishtijaiswal]

Bhaiya you are awesome the way you teach amazing thank you so much🔥🔥🔥

[tushar]

Sir as the array was not sorted initially, so how did u decide that we have to use binary search ? And how are we so confident while moving to one side that we'll find answer in that side only ?

[mohitranjan]

Sir which elements should be compared to determine the next half? mid < element, mid - 1 < element or mid + 1 < element?

[surajthapliyal]

whoa !! i literally binge watched all videos of this playlist . Amaazing and easy explanation .