Блог пользователя guacamolesyrup

Efficient searching algo
Автор guacamolesyrup, история, 6 лет назад, По-английски

Recently I have encountered a problem regarding searching.Any help would be appreciated.It says let, A be a sorted array(1-based index) of size n where n is even.A new array B is generated by swapping some elements in odd-numbered positions in the first half of A with some elements in odd-numbered positions in the second half of A.Note that elements in the even numbered positions are the same in both A and B, whereas each element in an odd-numbered position in A takes part in at most one swap.Write an algorithm that takes A and an integer x as inputs and finds whether x is present in B or not.

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

You can store the array in a map and then try to search the element because in map, time complexity of searching element by using the find function is O(logn). I hope it helps..

→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

B is basically reordered A (each element in an odd-numbered position in A takes part in at most one swap). Just do binary search on A. If X in A — it's in B.

→ Ответить