   recursive binary search
  So I am tracing through a binary search algorithm. I was looking through some notes that traced through all the comparisons between data and our target. For the case where n = 7, the first compared value was 4.  When we first call the search, however, bottom is passed in as 0, and top is passed in as list.size() - 1 (or 6 in our case).  The middle is determined by (top + bottom)/2.  Clearly middle would be 3 in this case.  And isn't the data we compare based on middle?  Why should we be comparing 4 to our target as opposed to 3?Here is the code:/*Post: If an entry in the_list has key equal to target, then returnsuccess and the output parameter position locates such an entrywithin the list.Otherwise return not_present and position becomes invalid.*/Error_code run_recursive_search_2(const List<Record> &the_list, const Key &target, int &position){  return recursive_binary_2(the_list, target, 0, the_list.size() -1, position);}  /* Pre: The indices bottom to top define the range in the list to search  for the target.  Post: If a Record in the range of locations from bottom to top in the_list  has key equal to target, then position locates one such entry and a code of  success is returned. Otherwise, the Error_code of not_present is returned  and position becomes undefined.*/Error_code recursive_binary_2(const List<Record> &the_list, const Key &target,int bottom, int top, int &position){  Record data;  if (bottom <= top) {    int mid = (bottom + top)/2;    the_list.retrieve(mid, data);    if (data == target) { position = mid; return success;    }    else if (data < target) return recursive_binary_2(the_list, target, mid + 1, top, position);    else return recursive_binary_2(the_list, target, bottom, mid - 1, position);  }  else return not_present;}I think I just figured it out...retrieve finds the the 4th index in our array when 3 in passed because the array starts at 0...  Would this be the case?[source lang="cpp']template<class List_entry>Error_code List<List_entry> :: retrieve(int position, List_entry &x ) const{  if (position < 0 || position >= count) {    return range_error;  }  x = entry[position];  return success;}
  Any particular reason you're doing it recursively? This algorithm is also easily expressed iteratively.That custom List class doesn't happen to be a linked-list with a custom operator[] that walks the list, does it? There's almost never a good reason to binary search on a linked-list. The running time of binary searching a linked-list is O(n) if you save where you were at each time you compare a node, or up to as bad as O(n*n) if you walk the list from the beginning each time, depending on how far through the list the item would be.You might like to read the article I wrote largely about binary searching.Whenever there is an odd number of items in the array being binary searched it should start with the middle item. For seven values that's item 4 (index 3)0 1 2 3 4 5 6When there is an even number if items (e.g. six) it does not matter whether you pick the last item of the lower half, or the first item of the upper half:0 1 2 3 4 5or0 1 2 3 4 5   