Hi all.

My beginner programming class has reached a section on sorting and searching arrays. On sorting, we've gone over the bubble sort and the selection sort. I'm trying to figure out the heap sort and quick sort on my own (we don't cover those in this particular class), but am having trouble with that. But that's a completely different matter all together.

On searching, we went over sequential and binary searching. I think I've got things down pretty well. No formal assignment has been given on sorting or searching, but I was noodling around in my compiler yesterday and I wrote something that seems to work.

Here's the binary search function I wrote. The array numbers[] is 30 randomly generated integers from 0-99. It is already sorted in ascending order by a selection sort prior to being passed to this function. Search is working, sort of. If a number repeats itself, it'll only inform you of the first occurrence of that number. I'm thinking that through, and maybe the solution to that will change the answer to my next question. But for now, let's assume that I don't care that it's always returning the first occurrence of a given number.

My question is more about code efficiency. The while loop that searches the array has this condition:

But I've been wondering, is it better to use a joint condition like that (I dunno if there's a more technical term), or to just do away with the first condition (and the boolean variable found)? I'm thinking that if, right after the line whereCode:while( (!found) && (bottom <= top) )foundis set to true, I add a line sayingbottom = top + 1, I can eliminate the first condition of the while loop and the logic remains the same. The search key is found, so set up a condition where the loop condition will evaluate as false, and the program stops searching the array. My thought here is that if you use TWO conditions for the while loop, the program needs to make TWO decisions at every iteration, effectively doubling the work.

The reason I bring this up is because when he was introducing the binary search, my instructor set up a code sample which did use a joint condition like the one I've used below. This professor can be a bit of a stickler for doing things the way he envisions them on the basis that code should be more efficient. I'm thinking that, actually, my code with one condition for the while loop is more efficient than code with two conditions. I know that in a small program like this there's virtually no difference, but in general, is my reasoning correct? And is it bad practice to tinker with your variables and intentionally set them to certain values for the express purpose of forcing a conditional statement to evaluate as false?

Code:void binarysearch(int numbers[],int size) { int key; int bottom; int middle; int top; bool found; bool searchagain = true; char choice[10]; while(searchagain) { bottom = 0; top = size; found = false; cout <<"\n\nWhat number to search for? "; cin >> key; while( (!found) && (bottom <= top) ) { middle = (bottom + top) / 2; if(numbers[middle] == key) { cout <<"\nI found " <<key <<" at position " <<middle <<"."; found = true; } if(key < numbers[middle]) //It's in the bottom half of the array. top = middle - 1; //New top is one before the midpoint. if(key > numbers[middle]) //It's in the top half of the array. bottom = middle + 1; //New bottom is one after the midpoint. } if(!found) cout <<"\nSorry, I couldn't find " <<key <<" anywhere."; cout <<"\nSearch again? "; cin >> choice; switch(choice[0]) { case 'Y': searchagain = true; break; case 'N': searchagain = false; break; default: cout <<"\nI don't understand that, so we're not going to search again."; searchagain = false; break; } } cin.get(); }

Tweet This+ 1 thisPost To Linkedin