Array Searching Algoritms II

This tutorial is a sequel to my previous tutorial on Array Searching Algorithms. Array Searching Algorithms II will teach you a much more efficient way of searching an array of data. As with the previous tutorial, a firm grasp on Arrays and the basics of the C++ language is required.

In my previous tutorial, Array Searching Algorithms 1, I presented the linear search algorithm as a simple way of searching short arrays. However, if you have an array of 10000 elements, the linear sort becomes rather ineffective. This is where the Binary Search algorithm comes in. The binary search algorithm starts searching for the value in the middle of the array. It then uses a divide and conquer strategy, dividing the list into smaller and smaller halves until it finds the value it's looking for. Because of the way the binary search algorithm functions, it requires the array to be in order. So lets look at some pseudo code to start off.


while the value hasn't been found and first is <= to last

	set middle to the (start + end array numbers) / 2

	if (array[middle] is the value being searched for)

	{

		set found to true

		set the position to middle

	}

	else if array[middle] is greater than the value

	{

		set last to middle minus 1

	}

	else

		set first to middle plus one

	return the position of the value

The psuedo code basically consists of a while loop that keeps going as long as we haven't found the value and the array were searching within dosen't have a length of zero (because the array being searched in gets continually smaller with every search). If first checks the middle position, and if the value isn't there, it either cuts off the lower or upper half of the array depending on whether the middle value was greater or less than the value being searched for. Once the value being searched for is found, it is stored in position and returned. Otherwise, -1 is returned to show that the algorithm didn't find the value being searched for.

So, now we just code straight from the pseudo code. We will type in the the rest of the C++ code before the binary search algorithm function (just to get it out of the way). Open up a new C++ file and type in the following.


#include <iostream>

using namespace std;


int searchArray(int[], int, int);


int main()

{

    int myArray[5] = {23, 34, 56, 89, 94};

    int value, result;

    

    cout << "Enter a value to search for: ";

    cin >> value;

    

    result = searchArray(myArray, 5, value);

    

    if (result == -1)

       cout << value << " was not found in the array." << endl;

    else

        cout << value << " was found at position " << result - 1 << " of the array. " << endl;

}

In this code, we are simply writing the main function in our sample program and setting it up to receive input, search the array, and output the result. We also declare the function prototype of the array searching function we will make now. Type the following into your C++ document below the code you just typed.


int searchArray(int array[], int numElems, int value)

{

    int first, last = numElems - 1,middle, position = -1;

    bool found = false;

    

    while(!found && first <= last)

    {

         middle = (first + last) / 2;

         

         if (array[middle] == value)

         {

              found = true;

              position = middle;

         }

         

         else if (array[middle] > value)

              last = middle - 1;

              

         else

              first = middle + 1;

    }

    

    return position;

}

Since this code is based off of the pseudo code we wrote previously, it has the same explanation. Declare variables to hold the first, last, and middle positions of the array as well as one to hold the return value of the function called "position". Also declare a boolean flag so that we can stop the loop when the correct value has been found. Enter the loop and continually divide the array into halves based on whether the middle of the array is greater than or less than the value we are checking for. When the value has been found, return it.

Now, a note on the basic functionality of this search method. The binary search requires that the array be in order to function properly. This is mostly due to the fact that the search algorithm determines the range it will search next based on whether the value it is currently checking is greater or less than the value it is looking for. If the array being searched is out of order, it will most likely return a value of -1 unless you get lucky. Regardless, in a real world application of this method, a sorting algorithm would be required to sort your array before allowing search with this method. Please see my previous tutorials on array sorting (Array Sorting Algorithms I, Array Sorting Algorithms II, Array Sorting Algorithms III) for examples of effective array sorting algorithms.

This code was written and compiled using Dev-C++. You may need to do some tweaking to run it in other compilers. The source code used in this project is attached for convenience. If you would like to contribute to the information presented here, or offer corrections, please post a reply. Thank you.

Attached Files

main..cpp 1.07K 49 downloads

outsid3r said:

This statement don't make much sense. Dev-C++ is not a compiler but an IDE, and there is nothing in your code that needs "tweaking" in order to compile it in other compilers. That kind of situations are really rare.

When I was programming in my first computer science class, we were using the Microsoft Visual Studio Express IDE. This IDE does not require you to send a "pause" command to the console when you have finished writing your code. When you hit "run" in the Microsoft IDE, the code would execute normally and the pause command would be added automatically. When I ran any applications separately on my home computer, the pause command was not added and I would get a flash of a black screen and the program would exit. Additionally, I have experienced the Microsoft IDE throwing errors when variable names are re-used in ANY scope. This is what I mean by "you may need to do tweaking for other compilers." Thank you for your observation.