Menu
Source : Microsoft Interview Question
Given a sorted array, in which every element is present twice except one which is present single time, we need to find that element.
Now a standard O(n) solution is to do a XOR of list, which will return the unduplicated element (since all duplicated elements cancel out.)
Is it possible to solve this more quickly if we know the array is sorted?
869
Approach based on Binary Search: The idea is the use Binary search because the array is sorted. Follow the steps mentioned below: Take the first number, then find its last occurrence or upper bound using binary search. Then count it as one unique element.
Search in a sorted infinite arrayWrite a function to return the index of the target if it is present in the array, otherwise return -1. Example 1: Input: [2, 5, 7, 9, 10, 12, 15, 16, 18, 20, 24, 28. 32, 35], target = 16 Output: 7 Explanation: The target is present at index '7' in the array.
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.
Yes, you can use the sortedness to reduce the complexity to O(log n) by doing a binary search.
Since the array is sorted, before the missing element, each value occupies the spots 2*k and 2*k+1 in the array (assuming 0-based indexing).
So you go to the middle of the array, say index h, and check either index h+1 if h is even, or h-1 if h is odd. If the missing element comes later, the values at these positions are equal, if it comes before, the values are different. Repeat until the missing element is located.
52
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
