Binary Search
Binary Search: When there is a large data structure, the linear search takes a lot of time to search the element. The binary search was developed to overcome the lack of a linear search. It is based on the divide & conquers principle. It is a very fast searching algorithm. The time complexity of the binary search is O (log n). A binary search can only be applied to a sorted list.
In this searching technique, the given element is compared with the middle element of the list.
- If both elements are equal, it returns the index value.
- If both elements are not equal, we check whether the given element is larger or smaller than the middle element.
- If the given element is smaller than the middle element, we will repeat the same process in the smaller part of the list.
- If the given element is larger than the middle element, we will repeat the same process in the larger part of the list.
Complexity of Binary search
Complexity | Best case | Average case | Worst case |
Time | O(1) | O(log n) | O(log n) |
Space | O(1) |
Algorithm of Binary search
Binary_Search( ) Step 1: SET BEG = lower_bound, END = upper_bound, FLAG = - 1 Step 2: Repeat Steps 3 and 4 while BEG <=END Step 3: SET MID = (BEG + END)/2 Step 4: if A[MID] = VAL SET FLAG = MID print “index value of the element” Go to Step 6 else if A[MID] > VAL else END = MID - 1 else SET BEG = MID + 1 // end of if // end of loop Step 5: if FLAG = -1 print " element is not found in this list " // end of if Step 6: exit |
For example, suppose you have the following array, and you have to search 30 in it.
Iteration 1: BEG = 0 END = 8 MID = (BEG + END) / 2 (0 + 8) / 2 = 4 A[MID] = VAL A[4] = 30 35 ? 30 // not equal Iteration 2: BEG = 0 END = MID – 1 = 4 – 1 = 3 MID = (0 + 3) / 2 = 1 A[1] = VAL 27 ? 30 // not equal Iteration 3: BEG = MID + 1 = 1 + 1 = 2 END = 3 MID = (2 + 3) / 2 = 2 A[2] = VAL 29 ? 30 // not equal Iteration 4: BEG = MID + 1 = 2 + 1 = 3 END = 3 MID = (3 + 3) / 2 = 6 A(3) = VAL 30 = 30 // equal Index value of 32 is 3. |
Binary search program in C language
#include<stdio.h> int binarySearch(int[], int, int, int); void main () { int arr[10] = {6, 9, 12, 23, 35, 46, 68, 90, 96, 120}; int item, location=-1; printf("enter the search element "); scanf("%d",&item); location = binarySearch(arr, 0, 9, item); if(location != -1) { printf("element index value is %d",location); } else { printf("element not found"); } } int binarySearch(int a[], int beg, int end, int item) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == item) { return mid+1; } else if(a[mid] < item) { return binarySearch(a,mid+1,end,item); } else { return binarySearch(a,beg,mid-1,item); } } return -1; }
Output
enter the search element 35 element index value is 4 |