Searching an element in a sorted array

I was applying for a position, and they asked me to complete a coding problem for them. I did so and submitted it, but I later found out I was rejected from the position. Anyways, I have an eclectic programming background so I'm not sure if my code is grossly wrong or if I just didn't have the best solution out there. I would like to post my code and get some feedback about it. Before I do, here's a description of a problem:


You are given a sorted array of integers, say, {1, 2, 4, 4, 5, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 11, 13 }. Now you are supposed to write a program (in C or C++, but I chose C) that prompts the user for an element to search for. The program will then search for the element. If it is found, then it should return the first index the entry was found at and the number of instances of that element. If the element is not found, then it should return "not found" or something similar. Here's a simple run of it (with the array I just put up):

Enter a number to search for: 4

4 was found at index 2.
There are 2 instances for 4 in the array.

Enter a number to search for: -4.

-4 is not in the array.

They made a comment that my code should scale well with large arrays (so I wrote up a binary search). Anyways, my code basically runs as follows:

• Prompts user for input.

• Then it checks if it is within bounds (bigger than a[0] in the array and smaller than the largest element of the array).

• If so, then I perform a binary search.

• If the element is found, then I wrote two while loops. One while loop will count to the left of the element found, and the second while loop will count to the right of the element found. The loops terminate when the adjacent elements do not match with the desired value.

EX: 4, 4, 4, 4, 4

The bold 4 is the value the binary search landed on. One loop will check to the left of it, and another loop will check to the right of it. Their sum will be the total number of instances of the the number four.

Any

I would have a few concerns about hiring someone who submitted this for a code sample. Here is what I see.

First, addressing overall design, the algorithm is suboptimal, and is worst case linear instead of worst case logarithmic, because it doesn't use a binary search to find the amount of elements, but a linear one.

Second, (and this is what would have really killed it for me) the variable names. Most of these are either one or two letters, and the code is very unreadable because of it. Giving your variables descriptive names is important for maintainability.

Third, ignoring standard libraries. Unless instructed not to use them, you should prefer standard libraries which have implementations of binary search (e.g. the stl or bsearch)

Fourth, why have get_num_of_ints return -1 has a magic value feeling to me; better to just set count = 0 and check that.

Fifth, get_num_of_ints is just far too long, and tries to do way too much. It badly needs to be broken up.

Sixth (and this is a personal choice), I think C++, with the STL, is a far better choice in this instance.

In the spirit of "show, don't tell", here is how I would have written the assignment (untested, uncompiled) (edited to match the required function signature):

#include 
#include 

using namespace std;

// This function signature is required:
int get_num_of_ints(const int* searchBegin, size_t searchSize, int input,
    size_t* first, size_t* count) {
  const int* searchEnd = searchBegin + searchSize;
  const int* result = lower_bound(searchBegin, searchEnd, input);

  if (searchEnd == result || *result != input)
    return -1;

  *first = result - searchBegin;
  *count = upper_bound(result, searchEnd, input) - result;
  return 0;
}

void print_search_results(const int* searchBegin, size_t searchSize, int input) {
  size_t first;
  size_t count; 

  if (get_num_of_ints(searchBegin, searchSize, input, &first, &count) > *input;
  cout << endl;    
  return succeeded;
}

int main (int argc, char** argv) {
  const int searchNumbers[] = {1, 2, 4, 4, 5, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 11, 13};
  const int searchNumbersSize = sizeof(searchNumbers)/sizeof(searchNumbers[0]);

  while(1) {
     int input;
     if(!read_input(&input)) {
       count << "Bad input, exiting" << endl;
       return 1;
     }

     print_search_results(searchNumbers, searchNumbersSize, input);
  }
}

StackExchange Code Review Q#4223, answer score: 111