A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyrights whatsoever.
In a binary search, the conventional method used is to determine the midpoint of a sorted list of items of data or a subset of a list by calculating the sum of the extreme pointers and then dividing by two. In a conventional binary search half of the remaining list is eliminated from the search by each comparison. When the searched item is not found, the pointers cross to indicate where that searched item would be inserted to be in sorted order. Given N items in a list, N/2 items on average must be physically moved to make room for a new item to be inserted in sorted order.