implement a method that given a sorted array with negative and positive values, find a value that is equal to its index. for example: [1, 2, 4, 5, 4] = will return 4. Do it with better complexity than O(n).

Question

implement a method that given a sorted array with negative and positive values, find a value that is equal to its index. for example: [1, 2, 4, 5, 4] => will return 4. Do it with better complexity than O(n).

Anonymous · Accepted Answer

you should run binary search on that array because its already sorted.
Each time you devide your array into 2 sub elements, check if the middle element is equal to its index than return it, otherwise if the middle element is lower than its index => check the left sub element otherwise => check the right sub element

Microsoft

Microsoft Interview Question

Interview Answer

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches