Consider the search problem for a sorted array of size n. What is the maximum number of distinct outcomes?
Answers
Answer:
O(logn) “Big O” notation denotes an upper-bound and only indicates an asymptotic general order of magnitude that the solution will be bound to worse-case, not any actual particular integer.
So the way to determine the actual worse case given a fixed number of items is to examine the mechanics of the algorithm and devise a worse-case scenario from that.
Binary search is a divide-and-conquer algorithm that splits its search range in half in a sorted set each iteration until it either finds its target or gets down to a set of 1 or 0 and fails. So a worse case will be searching for a non-existent item.
Binary search generally uses greater than, less than and equal to search an ordered set. By virtue of basic number theory, once a value is evaluated, the direction of the next boundary is given, so both sides do not need to be searched.
Example:
1000 items — integers sorted from 0 to 10,000
search for the number 604, that is NOT in the ordered collection.