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

Isn't $O(log\ n)$ ?

---

That array is not sorted?

---

Since we cannot make a calculative guess on the position of that element to drop a part of the array from search (like in binary search we drop half of the array) we have to visit all the elements.

Therefore, the worst case time complexity would be $O(n)$ where $n$ is the number of elements in that array.

---

O(n) you can use here the concept of counting sort......iff(max_element<=total size)

---

both time and space will take O(n)

---

No it can`t be ! @ prateekdwv  rightly said it!

Once you calculate the mid and apply logic that if $(a[mid]==a[--mid] \ || \ (a[mid]==a[++mid]) $ there is no further step to take therefore sequentially searching is best .

---

No assumption can be made over the elements stored in the array.

So we can sort the array first and then do linear search. Total time = O(nlogn) + O(n) = O(nlogn).

---

@shubhanshu why not to make binary search after sorting.?
anyhow complexity will remain same O(nlogn)

@hs_yadav we cannot use counting sort because reange of elements is not fixed here.

---

How will you do the Binary search?

---

Ashwin every element is repeated more than once except one. thats y binary search is inefficeant

---

we can apply xor operation for finding non repeated element which will take O(n)

---

Can you explain it in more detail?

---

If we can assume an extra space then we can use the hash table to mark the frequencies of each element, this will take O(n) time & space complexity. We can search through this hash table to find the element of frequency=1, this will be O(n) time.

---

then what would be your hashing function?

---

srivivek95 

time complexity to build hash table.....??

---

It's the mapping that we'll do for the "values" in the given array to the "indexes" of the second array. Second array elements are initially set equal to 0. We will iterate through the first array & increment the value in the second array corresponding to the index=value in second array.

---

I think Binary search with some modification can do this sucessfully.

The sequence for searching in the array will be like this:

Go to middle, check its left and right,

                        if both are different, then this is our element.

                        else we direct our search towards left or right as usual.

I don't think this will be skipping any elements, and it will successfully find the element in $O(logn)$.

@Tuhin Dutta check this. is this right?

---

See at the top i.e in the header I have mentioned that array is sorted but forgot to mention in the question.

---

@Shivansh, actually I also thought of the same algorithm.

---

@Shivansh Gupta,

else we direct our search towards left or right as usual.

here instead of word OR, it should be AND, because you are not sure where to go, and this AND makes difference from O(logn) to O(n)

the algorithm you have said, it will take O(n) time, because you are not throwing away half array at every iteration.
in worst case you you will end up searching entire array i.e O(n) 

---

you are not throwing away half array at every iteration.

@joshi_nitish, this is because we are not searching for a known element and thus ends up searching the whole array, $O(n)$.

right?

---

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.