[Bug 749653] dashdemux: Implement binary search for stream_sidx_seek

[GStreamer (GNOME Bugzilla)]

https://bugzilla.gnome.org/show_bug.cgi?id=749653

Edward Hervey <bilboed at bilboed.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
 Attachment #303693|none                        |needs-work
             status|                            |

--- Comment #2 from Edward Hervey <bilboed at bilboed.com> ---
Review of attachment 303693:
 --> (https://bugzilla.gnome.org/review?bug=749653&attachment=303693)

This looks wrong. The lowest entry it will return will be high / 2.

Say you have 200 entries. If your target ideal position is at 20, you will
never reach it, it will always return at least 100.

A proper binary search would do the following (while high != low):
1) split the search domain in two regions (low-mid and mid-high)
2) is the requested ts *in* the 'mid' entry? If so, stop here, we've found it
3) if not, figure out where the target ts is (in the lower or higher region ?)
and either adjust the 'high' or 'low' position accordingly
3.1) if ts < current mid, we know mid is the highest value, high = mid
3.2) if ts > current mid, we know mid is the lowest value, low = mid
4) recalculate mid = (high - low) / 2
5) goto 1)

That way you'd end up searching for less and less entries (200, 100, 50, 25,
12, 6, 3, 1) i.e. 8 steps instead of a max of 200 steps in the iterative case.

-- 
You are receiving this mail because:
You are the QA Contact for the bug.
You are the assignee for the bug.