Array search

Computer Science Level 3

Consider the problem of finding an element $x$ in an array of size $n$ . In which of the following cases can we find the element $x$ in $O(\log n)$ time?

A) Array is sorted.

B) Array is sorted and is rotated by $k$ . The value of $k$ is known.

C) Array is sorted and is rotated by $k$ . The value of $k$ is unknown.

D) Array is not sorted.

All

A

only

A

and

B

A, B

and

C

1 solution

展豪張
Mar 23, 2016

A nice question! (liked)
Answer is $A,B,C$ .
For $A$ simply use binary search. It's $O(\log n)$ .
For $B$ rotate it back first. Then use binary search. It's $O(1)+O(\log n)=O(\log n)$ .
For $C$ use binary search to find out value of $k$ first. Then rotate it back. Then use binary search. It's $O(\log n)+O(1)+O(\log n)=O(\log n)$ .

Can you explain how'll you find k using binary search in C?

Pranjal Jain - 5 years, 2 months ago

Since the array is sorted then rotated, it consists of two sorted array and there is one point in the middle that array[n]>array[n+1].
For example, it is like this:
Sorted: 1 2 3 4 5 6 7 8 9
Rotated: 5 6 7 8 [9 1] 2 3 4
We first obtain the values of first and last element: 5 4
Then we preform the binary search. If it is larger replace it with the first and vice versa.
Example:
$\color{#3D99F6}5$ 6 7 8 $\color{#D61F06}9$ 1 2 3 $\color{#3D99F6}4$ [5 4]
5 6 7 8 $\color{#3D99F6}9$ 1 $\color{#D61F06}2$ 3 $\color{#3D99F6}4$ [9 4]
5 6 7 8 $\color{#3D99F6}9$ $\color{#D61F06}1$ $\color{#3D99F6}2$ 3 4 [9 2]
5 6 7 8 $\color{#3D99F6}9$ $\color{#3D99F6}1$ 2 3 4 [9 1]
So we find the value of $k$

展豪張 - 5 years, 2 months ago

Array search

1 solution

0 pending reports