Data Structures - Arrays - Searching

In this tutorial we will learn to search element in an Array data structure.

Table of Content

• Searching
• Example

Searching

Searching is a process of finding a specific item in a collection of items. The time taken to find the item depends on the order of the collection of items. For example, if the collection is not sorted then we have to check all the items in the collection. And if the collection is sorted then we can using searching algorithm to find the item we are looking for.

Click here for searching algorithms.

The time complexity will depend on the searching algorithm used. For example, if the collection is sorted in ascending order and we are using Binary Search to find the item then the time complexity will be O(log₂n).

Example

In the following C++ program we are going to search for an item in an array of size 5. If the item we are looking for exists in the array then we will return the index where we found the item. If the item is not present in the array then we will return -1. We are returning -1 because for an array of size N the valid indexes are 0, 1, 2, ..., (N-1).

#include <iostream>
using namespace std;

const int SIZE = 5;
int arr[SIZE];
int END = -1;

void freshInsertElements()
{
  cout << "Inserting " << SIZE << " elements in the array arr..." << endl;
  int i;
  for (i = 0; i < SIZE; i++)
  {
    arr[i] = i + 1;
  }
  END = SIZE - 1;
}

void print()
{
  cout << "Printing the content of array arr..." << endl;
  int i;
  for (i = 0; i <= END; i++)
  {
    cout << "arr[" << i << "] = " << arr[i] << endl;
  }
  cout << endl;
}

int search(int value)
{
  int start = 0, end = SIZE - 1, mid = (start + end) / 2;
  while (start <= end && arr[mid] != value)
  {
    if (value < arr[mid])
      end = mid - 1;
    else
      start = mid + 1;
    mid = (start + end) / 2;
  }
  if (start > end)
    return -1; // key not found
  return mid;
}

void printIndex(int index, int value)
{
  if (index > -1)
  {
    cout << "Found " << value << " at index " << index << "." << endl;
  }
  else
  {
    cout << "Value " << value << " not found." << endl;
  }
}

int main(void)
{
  freshInsertElements();
  print();

  printIndex(search(3), 3);
  printIndex(search(10), 10);

  return 0;
}

Output

Inserting 5 elements in the array arr...
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5

Found 3 at index 2.
Value 10 not found.