IMPLEMENTATION OF BINARY SEARCH
Aim:
To write a C program for implementation of binary search.
Algorithm
1. Start
2. Input the number of elements in the array (n).
3. Input the sorted elements of the array (arr[]).
4. Input the element to search (key).
5. Set low = 0 and high = n - 1.
6. Repeat steps 7–9 while low <= high: 7. Set mid = (low + high) / 2.
7. If arr[mid] == key, then:
8. The element is found at index mid.
9. Output "Element found at index mid".
10. Stop.
11. Else if arr[mid] < key, then:
a. Set low = mid + 1. (Search the right half)
12. Else, set high = mid - 1. (Search the left half)
13. If the element is not found, Output "Element not found".
14. End
Program:
#include <stdio.h>
int binarySearch(int arr[], int size, int key) {
int low = 0, high = size - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1; // Element not found
}
int main() {
int n, i, key, result;
// Input the size of the array
printf("Enter the number of elements in the array: ");
scanf("%d", &n);
int arr[n];
// Input the elements of the array (should be sorted)
printf("Enter %d sorted elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
// Input the element to search
printf("Enter the element to search: ");
scanf("%d", &key);
// Perform binary search
result = binarySearch(arr, n, key);
// Output the result
if (result != -1)
printf("Element found at index %d\n", result);
else
printf("Element not found\n");
return 0;
}
Output:
Enter the number of elements in the array: 6
Enter 6 sorted elements:
12
56
58
78
85
94
Enter the element to search: 78
Element found at index 3
Result:
Thus the C program for the implementation of binary search was successfully
executed and verified.
