#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int counter_sequential_search = 0;
int counter_binary_search = 0;
int main(void)
{
int size, arr[10000], search_number;
srand ( time(NULL) );
size = sizeof(arr) / sizeof(int);
set_randoms(arr, size);
sort(arr, size);
search_number = rand() % 100 + 1;
if (binary_search(arr, size, search_number) != -1)
printf("found\n");
else
printf("not found\n");
if (sequential_search(arr, size, search_number) == 1)
printf("found\n");
else
printf("not found\n");
printf("counter_sequential_search = %d\n", counter_sequential_search);
printf("counter_binary_search = %d\n", counter_binary_search);
return 0;
}
int binary_search(int arr[], int size, int search_number)
{
int start = 0, end = size - 1, middle = (start + end) / 2;
while (start <= end)
{
counter_binary_search++;
if(arr[middle] == search_number)
return middle;
if(arr[middle] > search_number)
end = middle - 1;
else
start = middle + 1;
middle = (start + end) / 2;
}
return -1;
}
void sort(int arr[], int size)
{
int i, j, tmp, swap;
for(i = 0; i < size; i++)
{
swap = 0;
for(j = 0; j < size - i - 1; j++)
{
if(arr[j] > arr[j + 1])
{
tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
swap = 1;
}
}
if (swap == 0) break;
}
}
int sequential_search(int arr[], int size, int search_number)
{
int i;
for (i = 0; i < size; i++)
{
counter_sequential_search++;
if (arr[i] == search_number)
return 1;
}
return 0;
}
void set_randoms(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
arr[i] = rand() % 100 + 1;
}
/*
found
found
counter_sequential_search = 6463
counter_binary_search = 7
sequential search loop run 6463 times.
binary search loop run only 7 times...
*/
