When we're searching for items in an unsorted linear structure there's not much we can do to speed up the process. We can basically either start at the beginning and move forward, or start and the end and move backward, checking each item in the structure for what you're looking for.

template <typename T>
int LinearSearch( const vector<T>& arr, T findme )
{
  int size = arr.size();
  for ( int i = 0; i < size; i++ )
  {
    if ( arr[i] == findme )
    {
      return i;
    }
  }

  return -1; // not found
}

• We begin at the first index 0 and iterate until we hit the last index. Within the loop, if the element at index i matches what we're looking for, we return this index.
• If the loop completes and we haven't returned an index yet that means we've searched the entire structure and have not found the item.
  • In this case, it is not in the structure and we can throw an exception to \ be dealt with elseware or return something like -1 to symbolize "no valid index". This search algorithm's growth rate is O(n) – the more items in the structure, the time linearly increases to search through it. Not much we can do about that, which is why we have different types of data structures that sort data as it is inserted - more on those later on.

OK, but what if the structure is sorted?

We're going to be learning about sorting algorithms, so what if we happen to have a structure that is sorted? How can we more intelligently look for some value in the structure?

Let's say we have a simple array like this:

And we want to see if "dog" is in the array. We could investigate what the first item is (Hm, starts with an "a") and the last item ("f"), and realize that "d" is about halfish way between both values. Maybe we should start in the middle and move left or right?

• Index 0 is "aardvark". Index 5 is "fox". Middle value (0+5)/2 is 2.5 (or 2, for integer division). What is at position 2? – "cat". If arr[2] < findme, move left (investigate arr[1] next) Or if arr[2] > findme, move right (investigate arr[3] next).
• "d" is greater than "c" so we'll move right… Index 3 gives us "dog" - we've found the item! Return 3.

In this case, we basically have two iterations of a loop to find "dog" and return its index. If we were searching linearly, we would have to go from 0 to 1 to 2 to 3, so four iterations.

This still isn't the most efficient way to search this array - just starting at the midpoint and moving left or moving right each time. However, we can build a better search that imitates that first step: Checking the mid-way point each time.

Here is the code:

template <typename T>
int BinarySearch( vector<T> arr, T findme )
{
  int size = arr.size();
  int left = 0;
  int right = size - 1;

  while ( left <= right ) {
    int mid = ( left + right ) / 2;

    if ( arr[mid] < findme ) {
      left = mid + 1;
    }
    else if ( arr[mid] > findme ) {
      right = mid - 1;
    }
    else if ( arr[mid] == findme ) {
      return mid;
    }
  }

  return -1; // not found
}

With the binary search we look at the left-most index, right-most index, and mid-point. Each iteration of the loop, we look at our search value findme – is its value greater than the middle or less than the middle?