Searching an Array

One of the most common list operations is searching for an item. In this lesson, we'll consider searching an array for a value, determining whether a value is an array element, and, if so, the element's index. We discuss two search technniques, one that can be done on any list and one that requires the list to be sorted.

Contents

Linear search

Binary search

---

Linear search

Consider the following.

Problem: Find the location of a particular value in an array

With a linear search technique, you look at every element in the array, one-at-a-time beginning at the first. When the value is found, quit immediately. If you get through the entire array without quitting, then the search is unsuccessful -- the value is not in the array.

The method linearSearch() returns the index of the searched value in the array. If the value is not in the array, linearSearch() returns -1.

int LinearSearch (int a[], int aSize, int toFind) 
{ 
     // Look through all items, starting at the front. 
     for (int i = 0; i < aSize; i++)     
         if (a[i] == toFind)            
             return i; 
  
     // You've gone through the whole list without success.  
     return -1; 
}

Here is an array, which is a list of numbers.

  int list[12] = {3,15,2,8,7,1,14,38,10,-2,61,5};

Below we illustrate the call linearSearch(list,12,10).

The second illustration is for the call linearSearch(list,12,25). The search goes all the way to the end of the array, since 25 is not in the list.

The search can be shortened if you know something about the array. If the array is ordered, then you can quit as soon as you reach a value that is bigger than the one being searched.

---

Binary search

A binary search can be used on ordered arrays. The algorithm for a binary search is as follows.

• Compare the searched for value to the middle array item
  • value == middle ==> quit. You've found it.
  • value < middle ==> consider the sublist making up the first half of the array (before the middle item)
  • value > middle ==> consider the sublist making up the last half of the array (after the middle item)
• If you didn't find the value, repeat the search on the sublist. You are done as soon as you find the item or whenever the sublist that you are supposed to search is empty.

int binarySearch(int a[], int aSize, int toFind) 
{
    int start = 0;                        //the entire array is searched so we start with 0
    int last = aSize -1;                  //last is the last array index
 
    while (start <= stop)                  // while there is still a place to look.      
    {
  
         int middle = (start + stop) / 2;    // Look here first  
         if (toFind == a[middle])            // Found item. Quit. 
               return middle;   
         if (toFind > a[middle])             // Look in the last half 
               start = middle + 1;  
         else                                // OR look in the first half 
               stop =  middle - 1;
    } 
    //the element wasn't found
    return -1;
}

  int list[12] = {-2,1,2,3,5,7,8,10,14,15,38,61}; 
  int val;                     // An item to search for in the list 
  int psn;                     // Position of val in the list  
  // .. assign something to val   
  psn = binarySearch(list, 12, val);

binarySearch(list,12,10)    =   7