Register

Binary Stream

• retagged by
582 views
0 votes
0 votes
We have a run of 0's followed by the run of 1's and we have to find the point where first 1 will be present. We only know the start of the sequence but we have no idea about the end.

what should the best case complexity of this problem? Describe your approach.
• retagged by
User Avatar

1 Answer

Best answer
2 votes
2 votes

It can be done in O(log n)

first we search a[2] if not equal to 1 then a[4],a[8], a[16]....

we use two variables for this one which stores a[2n-1] and another which stores a[2n]

let us say that at a[1024]=0 and a[2048]=1

now we have a low and a high now we can apply binary search

complexity

traversing in power of 2 = (log n)

binary search  = (log n)

total complexity(log n + log n)=O(log n)

• edited by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
2 answers
1
dhruba asked Jun 5, 2023
1,151 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). How many comparisons are needed in the worst case scenario to determine that the key is not in the array?
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). ...
User Avatar
1 votes
1 votes
4 answers
2
Abhishek Kumar 38 asked Dec 15, 2018
2,116 views
Binary Search
There are two sorted list each of length n. An element to be searched in the both the lists. The lists are mutually exclusive. The maximum number of comparisons required using binary search and find its time complexity?
There are two sorted list each of length n. An element to be searched in the both the lists. The lists are mutually exclusive. The maximum number of comparisons required ...
User Avatar
2 votes
2 votes
4 answers
3
aditi19 asked Aug 20, 2018
2,629 views
Binary Search
for binary search in an array of n elements the average number of searches is $\left \lfloor \log_{2}n \right \rfloor$ or $\left \lceil \log_{2}n \right \rceil$ ?
for binary search in an array of n elements the average number of searches is $\left \lfloor \log_{2}n \right \rfloor$ or $\left \lceil \log_{2}n \right \rceil$ ?
User Avatar
0 votes
0 votes
1 answer
4
Sabir Khan asked Aug 8, 2018
1,087 views
Binary search
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is (A) (n) (B) (logn) (C) (log*n) (D) (1)
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is(A) (n)(B) (logn)(C) (log*n)(D) (1)
User Avatar
Link Copied!