Coding Interview Questions: No. 58 - Search in Adjacent Numbers
No. 58 - Search in Adjacent Numbers
Question: Given an array where two neighboring elements are adjacent (in absolute difference 1), can you write an algorithm to search an element in the array and return its position? If the element appears multiple times, please return the first occurrence.
For example, if given the array {4, 5, 6, 5, 6, 7, 8, 9, 10, 9} and an element 9, the element appears twice in the array, and the first occurrence is at position 7.
Analysis: The most simple and straightforward solution is to traverse the array and compare elements one by one. This strategy works for every array, and it does not utilize the property of the array where two neighboring elements are in absolute difference 1.
Let's try to search the first 9 from the array {4, 5, 6, 5, 6, 7, 8, 9, 10, 9}. Firstly we are at position 0 where the element 4 is. The difference between 9 and 4 is 5, so we move to the position 5. Why? Because the absolute difference between two neighboring elements is 1. If the numbers in the array is increasingly sorted, the element at position 5 is 9. If some elements decrease, 9 should sit on the right of position 5. Therefore, 5 is the leftmost possible position of the element 9.
Read full article from Coding Interview Questions: No. 58 - Search in Adjacent Numbers
No comments:
Post a Comment