6,994 views
7 votes
7 votes

Consider the problem of searching an element $x$ in an array $\text{arr}$ of size $n$. When can the problem can be solved in $O(\log n)$ time?

  1. Array is sorted
  2. Array is sorted and rotated by $k$. $k$ is given to you and $k \leq n$.
  3. Array is sorted and rotated by $k$. $k$ is NOT given to you and $k \leq n$
  4. Array is not sorted
 
(A) 1 Only
(B) 1 & 2 only
(C) 1, 2 and 3 only
(D) 1, 2, 3 and 4

I am clear with 1 and 2 option but not getting about option 3.
 

2 Answers

Best answer
10 votes
10 votes
lets analyze the options one by one....

1> Clearly binary search can be implemented if the array is sorted. Hence search can be performed in O(logn).

2>Lets take an example first..

Consider an array with elements 1234567. Now, suppose the array is rotated by 2 then the new array will be 3456712. Here k is 2. As, k is known to us finding the pivot point is easy it will be just = (n-1)-k ;where n is the size of the array. Here it is 4. Now, to search for an element divide the array in two subarrays . Now compare the number with the 0th element, if the number is greater than the 0th element then apply binary search in left subarray to pivot else apply binary search to right subarray...Hence searching can be performed in O(logn).

3>Here k is not known. Hence the pivot point is not known, if we can get the pivot point then we can apply the same method as above.

Now cosider the above example. The pivot point has the property that the pivot point element is the only element whose next element is smaller than it in the array.Hence we can find the pivot in O(logn) applying binary search like seaching. and the rest are same as above Hence the total complexity becomes O(logn)+O(logn)=O(logn).

Hence 1,2 and 3  are correct options
selected by
1 votes
1 votes
I think it can easily be done.... Consider the array 3456712 and i want to search for 1, say 'x'.
1> Find the mid element. (here 6)

2> If 0th element is greater than x then continue on right subarray.

    Else left subarray.

3> continue the process

 

By the above method you need not worry about K value.

Hope am not going wrong. comment if you find anything wrong.
Answer:

Related questions

0 votes
0 votes
2 answers
1
dhruba asked Jun 5, 2023
1,093 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...
0 votes
0 votes
1 answer
2
3 votes
3 votes
1 answer
3
Sanjay Sharma asked Feb 20, 2018
1,035 views
An array A is of length n has log( n) distinct numbers.What is the time complexity of sorting A by best comparison based algorithm ?
4 votes
4 votes
7 answers
4
pradeepchaudhary asked Jul 9, 2018
12,442 views
Q) Consider a sorted array of n numbers. What would be the time complexity of the best known algorithm to find a pair a and b such that |a-b| = k , k being a positive int...