Problem Statement
Consider the very traditional problem: Given is an array of N elements. This array is stored in memory and it is guaranteed to be sorted in strictly ascending order. You are given an element X and you are asked to determine whether it appears in the given array.
A worst-case optimal algorithm for this problem is the binary search algorithm.
This algorithm works as follows: Initially, all N elements are candidates for where the value X may be. As long as you have some candidates, you repeat the following:
- Pick the middle candidate. (If the current number of candidates is even, you can pick either of the middle two candidates.)
- Examine that candidate. If it's equal to X, we found it and the search terminates.
- If the examined candidate is greater than X, we know that all following elements in the array are also greater than X. (Remember that the array is sorted.) Thus, we eliminate the examined candidate and we also eliminate all candidates to its right.
- Conversely, if the examined candidate is smaller than X, we know that all preceding elements in the array are also smaller than X. Thus, we eliminate the examined candidate and we also eliminate all candidates to its left.
A nonbinary search is a search that only differs from the binary search in step 1 of the algorithm. The new step 1 looks as follows:
- If you can pick a candidate that would not be picked by binary search, pick such a candidate. Only if that is impossible (i.e., when there are at most two candidates), pick a candidate binary search could also pick.
Clearly, there can be many implementations of nonbinary search that differ in the strategy used to pick the candidate in step 1. (In particular, linear search - the search that examines all candidates from the left to the right - is one possible nonbinary search.) Which one of those strategies is the best one, and how many questions will it need to solve an array of size N?
More precisely, for the given N determine and return the smallest possible number Q with the following property: "There is an implementation of nonbinary search that will compute the correct answer for any array of length N and any X, and for each such input it will only examine at most Q elements."
Definition
- Class:
- NonbinarySearch
- Method:
- search
- Parameters:
- int
- Returns:
- int
- Method signature:
- int search(int N)
- (be sure your method is public)
Constraints
- N will be between 1 and 10^6, inclusive.
Examples
1
Returns: 1
Just like with traditional binary search, we have to examine the element to check whether its value is X or not.
3
Returns: 3
Here the nonbinary search already becomes worse than binary search. Let's call the three elements of the array A, B, C. We know that A < B < C. Binary search would start by examining B. If B = X, the search is done, if B is too large, we check A, and if B is too small, we check C next. In either case the binary search would examine at most two elements. As binary search starts by looking at B and we have other options, we must choose one of those. Without loss of generality, we start by examining A. If A turns out to be too small, we still have two candidates: both B and C can still be equal to X. There is no way to finish the search without examining them both, so in the worst case we will look at all three elements.
15
Returns: 6
Binary search would be done in four questions, but the best we can do with a nonbinary search is six. With 15 elements, binary search would start by looking at the middle element - the 8th smallest and at the same time the 8th largest one. One of several possible optimal ways to start a nonbinary search is by looking at the sixth smallest element. We will get one of three possible outcomes: We find the X we are looking for. We'll see a value greater than X. This will leave us with 5 candidates: the five elements smaller than the one we examined. We'll see a value smaller than X. This will leave us with 9 candidates. Suppose we are left with 9 candidates. The situation repeats itself in the second round: binary search would examine the middle one of those nine elements, so our nonbinary search must examine one of the other eight. And so on.
1000000
Returns: 22
The largest valid input. The best nonbinary search can always give a correct answer for 1,000,000 elements by examining at most 22 of them. (That's only a little worse than binary search, and it is much better than linear search.)
2
Returns: 2
4
Returns: 4
5
Returns: 4
6
Returns: 5
7
Returns: 5
8
Returns: 5
9
Returns: 5
10
Returns: 6
11
Returns: 6
12
Returns: 6
13
Returns: 6
14
Returns: 6
15
Returns: 6
16
Returns: 6
17
Returns: 6
18
Returns: 7
19
Returns: 7
20
Returns: 7
25
Returns: 7
33
Returns: 7
34
Returns: 8
50
Returns: 8
65
Returns: 8
66
Returns: 9
99
Returns: 9
129
Returns: 9
130
Returns: 10
136
Returns: 10
257
Returns: 10
258
Returns: 11
352
Returns: 11
513
Returns: 11
514
Returns: 12
769
Returns: 12
1025
Returns: 12
1026
Returns: 13
1417
Returns: 13
2049
Returns: 13
2050
Returns: 14
2781
Returns: 14
4097
Returns: 14
4098
Returns: 15
7413
Returns: 15
8193
Returns: 15
8194
Returns: 16
15759
Returns: 16
16385
Returns: 16
16386
Returns: 17
26388
Returns: 17
32769
Returns: 17
32770
Returns: 18
56772
Returns: 18
65537
Returns: 18
65538
Returns: 19
105540
Returns: 19
131073
Returns: 19
131074
Returns: 20
231076
Returns: 20
262145
Returns: 20
262146
Returns: 21
382148
Returns: 21
392150
Returns: 21
524289
Returns: 21
524290
Returns: 22
724292
Returns: 22
824294
Returns: 22
924296
Returns: 22
999999
Returns: 22
100000
Returns: 19