Write program for searching an element in a given array of elements {45, 23, 89, 20, 67, 22, 19, 10, 60, 24, 90, 76, 52, 4, 98, 56}. Search an element using linear search and recursive binary search.
AIM: To write a program for searching an element in a given array of elements using linear search and recursive binary search.
Algorithm:
Linear Search (key, array, num of elements (n)):
Step 1: set i to 1 and loop till n
Step 2: if key is equal to array[i] set c equal to i
Step 3: print element found at c + 1
Step 4: if not equal go to step 2 and set i = i + 1
Step 5: if i > n print element not found
Step 6: Exit
Binary Search (array, initial, end, key):
Step 1: Find the middle element of array using, middle = initial + end / 2
Step 2: if initial is greater than end value returns -1
Step 3: If middle = key, return index
Step 4: if middle > element, call the function with end_value = middle - 1
Step 5: if middle < element, call the function with start_value = middle + 1
Step 6: Exit
Code:
#include
#include
void linearSearch (int key, int array[100], int n)
{
int i, v;
for (i=1; i<=n; i)
{
if (key == array[i])
{
v = i;
printf ("\n Element found at %d\n", v+1);
}
}
}
int BinarySearch(int array[], int low, int high, int key)
{
if (low > high)
{
return -1;
}
int mid = (low + high) / 2;
if (array[mid] == key)
{
return mid;
}
else if (array[mid] > key)
{
BinarySearch(array, low, mid - 1, key);
}
else if (array[mid] < key)
{
BinarySearch(array, mid + 1, high, key);
}
}
void bubble_sort(int list[], int size)
{
int temp, i, j;
for (i = 0; i < size; i)
{
for (j = i; j < size; j)
{
if (list[i] > list[j])
{
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
}
}
int main()
{
int key, n,choice;
int array[]= {45,23,89,20,67,22,19,10,60,24,90,76,52,4,98,56};
n = sizeof(array) / sizeof(array[0]);
printf("The elements of the array are: - ");
for(int i = 0; i < n; i){
printf("%d ", array[i]);
}
printf("\n Enter the search key: - ");
scanf("%d", &key);
printf("\n Enter your choice: - \n1.Linear Search\n2.Recursive Binary Search\n");
scanf("%d", &choice);
if(choice == 1)
{
linearSearch(key, array, n);
}
else if(choice == 2)
{
bubble_sort(array, n);
int index = BinarySearch(array,0, n-1, key);
if(index == -1 )
{
printf("Element not found ");
}
else
{
printf("Element found");
}
}
else
{
exit(0);
}
return 0;
}
Output:
