Linear and a binary search over an arrays of integers.
/* 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};
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()
