Find the element that appears once in a sorted array.

Question

In a sorted array, every element is repeated more than once except one. what will be the time complexity to find that element in the worst case?

Comments

yes, exactly..

because at every iteration we are not sure of either to go left or right, therefore we will go in both direction and,

recurrence relation will be T(n) = T(n/2) + T(n/2) + O(1)

---

@Shivansh Gupta

in this if you use binary search algorithm then still you will have to check every element .......means we are not getting advantages of BS algorithm....?

---

@joshi_nitish this was really close to a potential mistake, thanks for correcting :)

Answer 1

My ans is O(N)

we can not apply binary search here  because after divided  in binary search we should clearly know that which direction we go further either right  of left but here it is not possible element can be present in both direction. so we have to apply linear search to find that element.

Here question is little bit tricky because  in given question array is sorted. but array is sorted it does not mean that we have to apply binary search for finding element.