Write a code to implement binary search program in c. Given a sorted array, we have to write a code to search an element in an array using binary search.
Binary Search
A Binary Search is used to search an element in a sorted array. In binary search, we first calculate the mid position of an array. Then, After that we compare element to be search to the middle element an array. If a value matches with the middle element then the index is returned otherwise the algorithm repeats if the value is less than or greater than the middle element.
A Binary search algorithm is efficient than the linear search algorithm. The time complexity of binary search is O(log(n)).
Important Points
i) A Binary search algorithm is applicable only for sorted values. An array should be sorted either in ascending or descending order.
ii) The time complexity of binary search is O(log(n)).
Linked List Interview Questions
Binary search implementation using Recursion
Binary Search Algorithm
Let’s check the algorithm of binary search.
i) Initialize two indexes low and high. Initialize the value of low to zero and high to n – 1 where n is the length of an array.
low = 0
high = N – 1
ii)
Run a loop while low is less than equal to high.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
while (low <= high) { /* The value of mid is calculate using the value of low and high indexes. */ mid = (low + high) / 2 /* If the value is found than return the position of mid . */ if(arr[mid]==value) { return mid } else if (arr[mid] >= value) { high = mid - 1 } else { low = mid + 1 } /* If value is not found. */ return -1 } |
Binary Search Program in C
We have discussed binary search and it’s algorithm. Let’s write a c code to implement binary search.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
/* * Binary Search Program in C */ #include<stdio.h> int main() { // Declare an array with sorted value int arr[] = {1,3,5,6,7,8,9}; // Let's assume value 8 needs to be search int num = 8; int low = 0, mid; int high = (sizeof(arr)/sizeof(arr[0]))-1; while(low <= high){ // Calculate mid value mid = (low + high)/2; if(arr[mid] == num){ printf("Number is found at %d index",mid); break; }else if(arr[mid] < num){ low = mid + 1; }else{ high = mid-1; } } // If number is not found printf("Number not found"); } |
Reference Books for Data Structure
For reference, you can read these good books for a data structure.
