Binary search

Question

Given a sorted array of n elements where other than one element x every other elenent repeat two times then how much time will it take to find position of x

Answer 1

I think we can do it in $log(N)$ complexity

consider the example

array$= [1,1,2,2,3,4,4] $and we need to find 3

now i will represent the indexes of the array also

$a[0]=1$

$a[1]=1$

$a[2]=2$

$a[3]=2$

$a[4]=3$

$a[5]=4$

$a[6]=4$

As 1st occurrence of an element is represented in even indexes and repeated occurrence of element is at odd index., algorithm will be like this

• So, find the middle.element
• if middle element index is even, then check if middle element is same as middle+1 element
• if it matches, then single element is in right half of array ,otherwise it is in left half
• if middle element is odd , then check , if middle element is same as middle-1 element
• if it matches, then single element is in right half of array ,otherwise it is in left half

Thus it will take $O(log n)$ complexity

link in geeksforgeeks https://www.geeksforgeeks.org/find-the-element-that-appears-once-in-a-sorted-array/

Comments

1 2 2 3 3 4 4
here 1st array index is 0 and last array index is 6
Now mid =(0+6)/2=3
a[3]=3
Now according to algo
is a[3]==a[2] ??
if yes go right side of a[3]
else go left side of a[3]

---

but algo is saying go to right for a[3]==a[4] so here we need to search in right half where 1 is not present

see the  algo( answered above by Albin Paul )

---

This algorithm is given for indices starting from 0 not 1

Answer 2

i think O(n)

Comments

i think we can apply binary sesrch because it is sorted array

---

just try with this 1,2,2,,3,3,4,4,5,5,10,10
now after finding mid as 4 how will u find 1 or say how will u decide to go to left or right

---

Actually, it can take n/2 times. rt?

Means assign 1st one and compare  with 2nd one

if it matches, then go to assign 3rd one

i.e, check like this

while(i<n)
{
    if(a[i]==a[i+1])
    a[i]=a[i+2];
    else
    int found=a[i];

}

 

---

may be for one of the case but  i think not for worst case where we need to traverse till last .A nd u r also saying tym is of O(n)???

Answer 3

This can be solved in time $O(logn)$ using binary search. Since we are given $n$, $n$ must be odd(all pairs except x). 

If the element at index $mid =( 0 + n -1)/2$ is $  x$, we are done. Otherwise say its $array[mid] = y$.

For simplicity assume that $mid$ is even and if $array[mid] = array[mid-1] $, then $x$ must be present in the left half of the array. The reason is that the number of elements from $0$ to $mid - 2$ is odd(because of x) and the array is sorted.

If   $array[mid] = array[mid+1]$  , then $x$ must be present in the right half for similar reasons. 

Now assume that $mid$ is odd and if $array[mid] = array[mid-1] $, then $x$ must be present in the right half of the array. The reason is that the number of elements from $mid+1$ to $n- 1$ is odd(because of x) and the array is sorted.

If   $array[mid] = array[mid+1] $ , then $x$ must be present in the left half for similar reasons.  Recursively solve the problem using this approach using binary search.