Home > Articles, Data Structures & Algorithms > Implementation of sequential and binary search (iterative version).

Implementation of sequential and binary search (iterative version).

September 29, 2010 Leave a comment Go to comments

Sequential Search.

This algorithm checks whether the number ‘v’ is contained in a set of numbers already stored in the data a[0], a[1], …, a[r-1] of the array ‘a’ (where ‘r’ the number of elements in it), comparing it sequentially with all numbers, starting from the beginning. If the check reaches the end without finding the number, the value -1 is returned. Otherwise, we are returned the index of the position of the one-dimensional array containing the number.

int
search (int a[], int v, int r) {
  for (int i = 0; i < r; i++)
    if (v == a[i])
      return i;

    return -1;
}

Binary Search.

This algorithm checks whether the number ‘v’ is contained in a set of numbers already stored in the data a[0], a[1], …, a[r-1] of the array ‘a’ (where ‘r’ the number of elements in it). If the check reaches the end without finding the number, the value -1 is returned. Otherwise, we are returned the index of the position of the one-dimensional array containing the number. For the binary search to function properly, the elements of the array should first be sorted in ascending order.

int
search (int a[], int v, int r) {
  int l = 0;
  while (r - l > 1) {
    int m = l + (r - l) / 2;

    if (a[m] > v)
      r = m;
    else
      l = m;
  }

  return (a[l] == v) ? l : -1;
}
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: