BrowserUk,
Since this was a "one and done" script, I didn't really care too much about this being as efficient as possible. I ended up just performing 2 binary searches (to find each end point) and then reverted to a linear search to handle the duplicates.

Regarding the statement: I don't believe it is possible to code a search over sorted data with duplicates that comes even close to be O(log N). Even in theory. And in practical implementations, it'd be far slower.

Why would the following logic be so much slower in implementation?

  1. Perform a normal binary search to find the target item
    • If not found, check if $list[$mid] < $val to determine if $mid has to be adjusted by one to meet $anchor/$desired_operator - done
    • If found, proceed to step 2
  2. Determine if you are at "right" endpoint of the list of duplicates by checking the $list[$mid - 1] eq $val or $list[$mid + 1] eq $val
    • If yes, done
    • If no, proceed to step 3
  3. Check to see if this item is even a duplicate by checking $list[$mid - 1] eq $val or $list[$mid + 1] eq $val - whichever one not done in step 2
    • If not a duplicate - done
    • If a duplicate - proceed to step 4
  4. Use the following logic to find the first element in the desired direction that is not a duplicate. For the description, let's say I am trying to find the last element. $min = $mid from previous search and $max = $#list.
    • If $list[$mid] eq $val, $min = $mid
    • If $list[$mid] ne $val, $max = $mid - 1
    • Stop when $max - $min < 2

Cheers - L~R

In reply to Re^4: Modified Binary Search by Limbic~Region
in thread Modified Binary Search by Limbic~Region

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.