Question 1:
There is a sorted array which is shifted by some position:
Original Arr1: 1 2 3 4 5 7 8 15
Shifted array Arr2: 5 7 8 15 4 3 2 1
in Arr1 a searching a number can be done on log(n) using binary search. How will you search for a number in Arr2 in logn(n ) ?
Answer 1:
use the same logic as binary search, the only difference is that the below logic needs to be used for searching left and right indices
num is number to be searched
l is the left index, This is initialized to 0
r is right index, initialized to MAX -1
m = (l+r) /2
Algo:
m = (l+r)/2
if (( num <> arr2[m] ))
r = m
else if (( num < arr2[m]) && ( arr2[m+1] < arr2[m] ))
l = m
else if (( num > arr2[m]) && ( arr2[m+1] > arr2[m] ))
l = m
else if (( num > arr2[m]) && ( arr2[m+1] < arr2[m] ))
r = m
