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 );
    }
}

[download]

In reply to Re: Special binary search by Corion
in thread Special binary search by olepi

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.