The binary search is one of the common techniques to find a given key in a sorted list.

The following code shows this algorithm

[code language=”c”]
#define DATA_TYPE int
#define DATA_SIZE 65536
#define LOG_DATA_SIZE 16
void binary_search_core(DATA_TYPE ordered_data[DATA_SIZE], DATA_TYPE d, int *index) {

int left = 0;
int right = DATA_SIZE-1;
int location = -1;
int middle;

for (int j = 0; j < LOG_DATA_SIZE+1; j++) {
#pragma HLS UNROLL
middle = (left+right)/2;
DATA_TYPE m_d = ordered_data[middle];
if(d < m_d) { right = middle-1; }else if(d > m_d) {
left = middle+1;
} else {
location = middle;
break;
}
if (left > right)
location = -1;
}
*index = location;
}
[/code]