Here is an implementation of binary search. Please give feedback on any part but a few specific areas I was wondering about.
- Is
size_tused appropriately or shouldintorunsigned intbe used instead? - How can I shorten
selfTest()and in general make it better? I know it's clunky how it returns a value and prints an error message tostd::cout.
#include <iostream>
#include <cmath>
/*function prototypes*/
int selfTest();
int binarySearch(const int data[], const size_t length, const int findMe);
int main()
{
auto failed = selfTest();
std::cout << "failed tests: " << failed << std::endl;
return 0;
}
int binarySearch(const int data[], const size_t length, const int findMe)
{
size_t start = 0;
size_t end = length - 1;
while(start <= end)
{
const auto mid = start + ((end - start) / 2);
if(data[mid] < findMe)
{
start = mid + 1;
}
else if(data[mid] > findMe)
{
end = mid - 1;
}
else
{
return mid;
}
}
return -1;
}
int selfTest()
{
auto failed = 0;
int test1[7] = {1,2,3,4,5,6,7};
int test2[8] = {1,2,3,4,5,6,7,8};
int test3[7] = {1,2,3,4,5,7,7};
int test4[8] = {1,2,3,4,5,7,8,8};
int test5[3] = {1,2,3};
int test6[3] = {5,5,5};
int test7[5] = {-10, -2, 5, 6, 10};
int result;
result = binarySearch(test1, 7, 4);
if(test1[result] != 4)
{
std::cout << "Test A failed. Expected 2, got " << result << std::endl;
failed++;
}
result = binarySearch(test1, 7, 1);
if(result != 0)
{
std::cout << "Test B failed. Expected 0, got " << result << std::endl;
failed++;
}
result = binarySearch(test1, 7, 2);
if(result != 1)
{
std::cout << "Test C failed. Expected 1, got " << result << std::endl;
failed++;
}
result = binarySearch(test2, 8, 5);
if(result != 4)
{
std::cout << "Test D failed. Expected 4, got " << result << std::endl;
failed++;
}
result = binarySearch(test3, 7, 7);
if(test3[result] != 7)
{
std::cout << "Test E failed. Expected 5, got " << result << std::endl;
failed++;
}
result = binarySearch(test4, 8, 8);
if(result != 6 && result != 7)
{
std::cout << "Test F failed. Expected 6 or 7, got " << result << std::endl;
failed++;
}
result = binarySearch(test5, 3, 1);
if(result != 0)
{
std::cout << "Test G failed. Expected 0, got " << result << std::endl;
failed++;
}
result = binarySearch(test6, 3, 5);
if(result != 0 && result != 1 && result != 2)
{
std::cout << "Test H failed. Expected 0 or 1, got " << result << std::endl;
failed++;
}
result = binarySearch(test6, 3, 0);
if(result != -1)
{
std::cout << "Test I failed. Expected -1, got " << result << std::endl;
failed++;
}
result = binarySearch(test7, 5, -10);
if(test7[result] != -10)
{
std::cout << "Test J failed. Expected 0, got " << result << std::endl;
failed++;
}
result = binarySearch(test7, 5, -2);
if(test7[result] != -2)
{
std::cout << "Test K failed. Expected 1, got " << result << std::endl;
failed++;
}
result = binarySearch(test7, 5, 6);
if(test7[result] != 6)
{
std::cout << "Test L failed. Expected 3, got " << result << std::endl;
failed++;
}
return failed;
}