|
|
|
|
|
by SmartHypercube
809 days ago
|
|
If we ignore the information contained in the score numbers, only comparing which score is higher, we could optimize using ternary search (or golden-section search). https://en.wikipedia.org/wiki/Golden-section_search (Note that binary search does not apply here. This is searching for an extremum, not a zero point.) - Start at the range of 0-F, measure the score of 6 and 9 (2 tries)
- Depending on which is higher, narrow the range to 0-9 or 6-F
- Suppose the range is 0-9, measure the score of 3 and 6 (1 try. 6 is already measured)
- Narrow the range to 0-6 or 3-9
- Suppose the range is 0-6, measure the score of 2 and 3 (1 try. 3 is already measured)
- The worse case is 3's score is higher. The range is now 2-6. Since 2, 3, 6 are all measured, in the worst case you need 2 more tries for 4 and 5.
- The other case is 2's score is higher. The range is now 0-3 and 0, 2, 3 are all measured.
So in worst case there are 6 tries per slider. ~5 tries on average. I suspect this can be further optimized but I'll stop here :) |
|