Mfcttrf

Question

Any way I can optimize this further with C++11 or C++17 features?

Would also like feedback on my variable naming, memory management, edge case handling (in this someone calling my function with an nullptr or int overflow with my rearranged equation to calculate the mid), and coding style. If there are other data structures I can use to implement this instead of basic arrays and raw pointers I'd like some feedback there too.

For my return type on the binary_search function, does it matter if I return a bool versus an int?

Code

#include <cassert>
#include <iostream>

bool binary_search(int* data, int num_elements, int target)

 int low = 0;
 int high = num_elements - 1;
 int mid;

 if(data == nullptr) throw std::exception(); 

 while(low <= high) 
 mid = low + (high - low) / 2;
 if(data[mid] == target) 
 return 1;
 else if(data[mid] > target) 
 high = mid - 1;
 else 
 low = mid + 1;
 
 

 return 0;


int main()

 int num_elements = 6;

 int data[] = 5, 8, 10, 15, 26, 30 ;
 int target[] = 5, 4, 12, 15, 35, 30 ;
 int expected[] = 1, 0, 0, 1, 0, 1 ;

 for(int i=0; i < num_elements; ++i) 
 try 
 assert(expected[i] == binary_search(data, num_elements, target[i]));
 std::cout << expected[i] << " returned for search on " << target[i] << 'n';
 catch(std::exception& e) 
 std::cout << "Exception " << e.what() << 'n';
 
 

 return 0;

• 
  

  An idiomatic approach

  
  
  

  
  

  to implement this instead of basic arrays and raw pointers

  
  

  
  
  

  is to use iterators.

  
  



• Returning bool is dubious. The situation where I only want to know if the element is present or not is very rare. Typically I want to know where exactly the element is (or, if absent, where it should be inserted to keep the collection sorted). Your function does compute this information, but immediately throws it away. Return an iterator.



• 
  

  All that said, consider the signature

  
  
  

  template<typename It, typename T>
  It binary_search(It first, It last, const T& target)
  

  
  
  

  It is now suspiciously similar to the standard library's std::lower_bound. Follow the link for further insight and inspiration.

  
  

Considering you are using the same numbers as their example, I assume you're already aware of the binary search algorithm.

• Regarding coding style I prefer a space between flow control statements and the parenthesis but that is purely subjective.




• Don't compare to nullptr. Do if (!data) instead.




• IMO Not much use in printing out what() if you don't provide (meaningful) messages along with your exception.
  
  Could also specialize it.
  
  e.g.: std::invalid_argument("no input provided").




• Could use brace initialization if you want to use more modern C++ features (nitpick: mid is not initialized).




• Why didn't you use vector? It's pretty much a drop-in replacment. You could then also use the range for loop.




• return 0 is implicit in main.