Register

Binary search

• retagged by
1,480 views

2 Answers

1 1 vote

The Best way to find out whether an integer appears more than n/2 times in a sorted array(Ascending Order) of n integers, would be binary search approach.

1. The First occurrence of an element can be found out in O(log(n)) time using divide and conquer technique,lets say it is i.

2. The Last occurrence of an element can be found out in O(log(n)) time using divide and conquer technique,lets say it is j.

3. Now number of occurrence of that element(count) is (j-i+1). Overall time complexity = log n +log n +1 = O(logn).

Hence answer is Option B

Voting & Accepting an answer helps improve the community
Answer:
← Previous · Ace materialNext → · Invertible Matrix
← Previous in category · self doubtNext in category → · Time Complexity
Position:
Show:

Related questions

2 2 votes
2 2 answers
213
213 views
GO Classes asked Aug 12
213 views
GO Classes DPP | GATE CS, DA | Algorithms | Binary Search Insertion
Suppose Binary Search is used in Insertion Sort to locate where the $i$th element should be inserted among the first $i-1$ elements.What is the worst-case running time of...
0 0 votes
2 2 answers
1.9k
1.9k views
dhruba asked Jun 5, 2023
1,901 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). Ho...
0 0 votes
1 answers 1 answer
1.2k
1.2k views
shweta sah asked Jun 22, 2018
1,229 views
Binary search
Find the average number of comparisons in a binary search on a sorted array of 10 consecutive integers starting from 1.1) 2.62)2.73)2.84)2.9
4 4 votes
1 1 answer
1.9k
1.9k views
Aghori asked Nov 5, 2017
1,886 views
Binary search on two mutually exclusive arrays.
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 require...