Problem Statement -
In a sorted array, the odd indices are divided in two parts. Elements on left are swapped with elements on right. We have to search for index of a given number in that array.
Example -
"""
A = [1, 6, 3, 4, 5, 2]
B = 5
Ans = 4
"""
To Find = index of B.
Approach - We need to solve it in logN. So, we need to use binary search. But, it applies only on sorted arrays.
So, we apply binary search on even indices as they are sorted and try to find B or the number closest to B.
case 1: We are able to find B.
We return the index.
case 2: We are not able to find B.
So, we find the number next to our result. This is where B should reside in a sorted array. so, If that's equal to B we return it else, the number we found is the one that got swapped with B.
to_find = A[ans + 1]
So, we try to do binary search over even indices and find to_find.
Again, If A[ans] = to_find we return it, else we check for + 1 index.
Solution
class Solution:
# @param A : list of integers
# @param B : integer
# @return an integer
def solve(self, A, B):
lo = 0
hi = (len(A)-1)//2
ans = float('-inf')
ans_idx = None
# first search over all even indices
while lo <= hi:
mid = (lo + hi)//2
if A[mid * 2] == B:
return mid * 2
else:
if A[mid * 2] > B:
hi = mid - 1
else:
ans = max(ans, A[mid * 2])
ans_idx = mid * 2
lo = mid + 1
if A[ans_idx + 1] == B:
return ans_idx + 1
to_find = A[ans_idx + 1] # this is the number that was swapped
# in binary search try to find, this smaller or larger number.
lo = 0
hi = (len(A)-1)//2
ans = float('-inf')
ans_idx = None
# first search over all even indices
while lo <= hi:
mid = (lo + hi)//2
if A[mid * 2] == to_find:
return mid * 2
else:
if A[mid * 2] > to_find:
hi = mid - 1
else:
ans = max(ans, A[mid * 2])
ans_idx = mid * 2
lo = mid + 1
# print('ans', ans_idx, to_find, ans)
if A[ans_idx + 1] == B:
return ans_idx + 1
return - 1
Top comments (0)