Register

Finding Minimum

• retagged by
312 views

1 Answer

Best answer
1 votes
1 votes

The best way to solve such a problem is by using Binary Search. Search the sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half.

Find mid element

  • Is mid = 1 ?
  • Is mid >1?(not possible here)
  • Is mid < 1 ?

Proceed accordingly, the Worst case of this problem will be 1 at the end of the array i.e 00000…..1 OR 1…….0000. It will take log n time worst case.
n=31, Hence log 231 = 5.

Therefore, answer will be 5.

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

Related questions

2 votes
2 votes
1 answer
1
Harikesh Kumar asked Jul 10, 2017
502 views
Gate algorithm
User Avatar
14 votes
14 votes
4 answers
2
Arjun asked Feb 18, 2021
11,947 views
GATE CSE 2021 Set 2 | Question: 8
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$? $\Theta ( \sqrt{n})$ $\Theta (\log _2(n))$ $\Theta(n^2)$ $\Theta(n)$
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$?$\Theta ( \sqrt{n})$$\Theta (\log _2(n))$$\Theta...
User Avatar
0 votes
0 votes
1 answer
3
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!