Binary Search in HLS

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

The following code shows this algorithm

#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;
}