Method and apparatus for determining a next address within a binary search algorithm

Abstract

A method and apparatus are presented for implementing the next-address determination within a binary search algorithm. A binary search algorithm searches for a compared within a one dimensional sorted array of elements. Typically, a binary search algorithm comprises a comparator and a next address generator. The next address generator determines the address of the next array element (the “next address”) a comparator will search using both a “compared is greater” signal from the comparator and a signal which indicates the address of the last array the comparator searched (the “previous address”). The time needed to search an array for a compared inserts a delay in applications where a binary search algorithm is employed. One method of expediting the searching process is to minimize the number of gates between the input and output of the next address generator (the “critical path”). In an embodiment of the present invention, two gate levels are used within the critical path to increase the rate at which a search can be performed even when the search is interrupted and resumed after performing some other task.