Re: Special binary search

[Corion]

I'm not sure I understood your question correctly, but if I did, maybe your search is just two binary searches, one for the minimal element next larger than MIN and one for the maximal element smaller than MAX?

Once you have found these elements, you know the remaining elements for which you need to run your slow process.

Maybe if you show more examples and code, I understand where the problem is. Maybe this is enough of a testbed?

#!perl
use strict;
use warnings;
use feature 'experimental::signatures';
use Memoize;

my @values = (0,0,0,1,2,3,4,5,10,101,102,103);
my $MIN = 1;
my $MAX = 10;

# this is the slow part:
sub get_element_value( $index ) {
    sleep 1;
    return $values[$index]
};

# Cache indices that we have fetched once already
memoize 'get_element_value';

sub get_index_of_element_larger_than( $value, $low, $high ) {
    my $next_try = int(($low+$high) / 2);
    my $v = get_element_value( $next_try );
    if( $v > $value ) {
        return get_index_of_element_larger_than( $low, $next_try-1 );
    } else {
        return get_index_of_element_larger_than( $next_try+1, $high );
    }
}

[olepi]

This looks good, thanks!

Yes, two binary searches is what is needed. Once I find the two values bordering the window, I can then just run all the elements between them.

Fantastic! -- Bill P

[sn1987a]

Since you want all of the values within the window, there is no need to do two searches. Once you find one value in the window you can get sequential values, both higher and lower, until get the ends of the window.