/*  This application presents a linear and a binary search over an arrays of integers
 *
 *  In a linear search we check one value after the other and find out what is 
 *  the index of the searched of value 
 *
 *  A linear search does not requires that the values in the array are ordered
 *
 *  A binary search requires that the values in the array are sorted
 */
#include <stdio.h>


/* Search the target in the array, that holds len elements. In case the target is not found the
 * function returns -1, otherwise it returns the target position
 */
int linearSearch (int numbers[], int len, int target) {
      int index = 0;
      while (index < len) {
         if (target == numbers[index])
            return index;  // target found
         index++;
      }
      return -1;  // target not found
}  // Of linearSearch

/* Search the target in an array that holds len elements. The array is sorted in an ascending order
 * At each loop instance the range of the searched area is divided by 2 and the search is continues
 * on one of the two ranges. 
 *
 * In case the target is not found the function returns -1, otherwise it returns taget positon
 */

int binarySearch (int numbers[], int len, int target) {
      int index, left = 0, right = len - 1;

      while (left <= right) {
         index = (left + right) / 2;
         if (target == numbers[index])
            return index;  // target found
         if (target > numbers[index])
            left = index + 1;
         else
            right = index - 1;
      }
      return -1;  // target not found
}  // Of search


void main () {
      int numbers[] = {7, -3, 7, 2, 8, -1, 3, 2, 5, 6, 7};
	  int sortNumbers[] = {-3, -1, 2, 2, 3, 5, 6, 7, 7, 7, 8};
	  char atrArr[] = {
	  int len = sizeof(numbers)/sizeof(int);
	  printf ("The index of 6 is %d\n", linearSearch (numbers, len, 6));
      printf ("The index of 6 is %d\n", binarySearch (sortNumbers, len, 6));
}  // Of main()
Published in: C++
Download

Related snippets