Objective: C program to perform binary search operation using the divide and conquer technique.
Concept: A binary search tree is a binary tree. It may be empty. If it is not empty, then it satisfies the following properties:
1. Every element has a key and no two elements have the same key.
2. The keys (if any) in the left sub tree are smaller than the key in the root.
3. The keys (if any) in the right sub tree are larger than the key in the root.
4. The left and right sub trees are also binary search trees.
Algorithm:
Step 1: Start
Step 2: Declare the variables.
Step 3: Enter the list of elements using the get function.
Step 4: Divide the array list into two halves the lower array list and upper array list.
Step 5: It works by comparing a search key k with the arrays middle element a[m].
Step 6: If they match the algorithm stops; otherwise the same operation is repeated recursively for the first half of the array if k < a[m] and the second half if k > a[m].
Step 7: Display the searching results
Step 8: Stop
Time complexities: For Searching the element the worst case time complexity is O(n) and average case is O(log n).
#include <stdio.h>
Void main()
{
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements\n");
scanf("%d",&n);
printf("Enter %d integers\n", n);
for(c =0; c < n;c++)
scanf("%d",&array[c]);
printf("Enter value to find\n");
scanf("%d",&search);
first =0;
last = n -1;
middle =(first+last)/2;
while(first <= last)
{
if(array[middle]< search)
first = middle +1;
else if(array[middle]== search)
{
printf("%d found at location %d.\n", search, middle+1);
break;
}
else last = middle -1;
middle =(first + last)/2;
}
if(first > last)
printf("Not found! %d is not present in the list.\n", search);
getch();
}
