Hacker News new | ask | show | jobs
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 :)