**Binary Search**is used to find the given element in a

**sorted**array of elements. This is one of the best searching algorithm. It follows the method

**devide and conquer.**And the

*time complexity*for this searching algorithm is

**O(log(n))**where n is no.of elements in the array. Binary search is very usefull if the no. of elements are more. The pre-condition to use this method is that input array should in sorted array. Otherwise it wont work.

**How Binary Search works:**It will search for the element

*key*in a sorted array of elements in such away that, it finds the middle element of the array by getting average of starting and ending postions of the array, if the middle element is

*key*, search stops and returns the position of the element other wise

*key*will be compared with mid element, and if the mid element is greater than the

*key*value, starting index of the array changes to

*mid+1,*and the mid value is less than the

*key*value, ending index of the array changes to

*mid-1.*This process continues until

*key*value finds or starting index greater than equal to the ending index.

**Algorithm for Binary Search:**

1. Get the

*key*element which needs to be searched

2. Get the sorted

*array*in which

*key*needs to be searched

3. Find the

*mid*value of the array by findings (

*startIndex*+

*endIndex*)/2

4. If

*key*value is equals the

*array*[

*mid*] value , returns

*mid*value and stop the search

5. If the

*key*value greater than

*array*[

*mid*] value, change the

*startIndex*to

*mid+1*and goto step 3.

6. If the

*key*value less than

*array*[

*mid*] value, change the

*endIndex*to

*mid-1*and goto step 3.

7. Repeat the steps 3 to 6 until

*startIndex*greater than equal to the

*endIndex*.

**Function Prototype for Binary Search:**This function will takes the input values like array of elements,key which needs to be searched in the array, starting posting of the array and ending position of the array. It will return the position of the finding element or -1 if not found in the array.

/**************************************************************** Name: binary_search Input: array , key , max_pos, min_pos Return type: int ****************************************************************/ int binary_search(int arr[],int key,int min_pos, int max_pos) { while(max_pos >= min_pos) { //finding the middle element int mid = (min_pos + max_pos)/2; // if mid element is less than key, need to change min_pos value if(arr[mid]<key) min_pos = mid+1; // if mid element is greate than key, need to change max_pos value else if(arr[mid]>key) max_pos = mid-1; // else got the position else return mid; } //other wise not in the array return -1; }

**Time Complexity:**The time complexity of the Binary search is

**O(log(n)).**This is because, each time it will eliminate half of the array. So at max we will get

**log(n)**iteration to search. Assume that if the array has 8 elements, for first iteration, we will get 8/2 which is 4 and for second iteration we will get 4/2 which is 2 and in third itetation we will get 2/2 which is 1. Like this if the elements are 128, we will get in log(128) iteration which is 7 iterations.

**Program of Binary search in C:**Below is the binary search C code.

#include/**************************************************************** Name: binary_search Input: array , key , max_pos, min_pos Return type: int ****************************************************************/ int binary_search(int arr[],int key,int min_pos, int max_pos) { while(max_pos >= min_pos) { //finding the middle element int mid = (min_pos + max_pos)/2; // if mid element is less than key, need to change min_pos value if(arr[mid]<key) min_pos = mid+1; // if mid element is greate than key, need to change max_pos value else if(arr[mid]>key) max_pos = mid-1; // else got the position else return mid; } //other wise not in the array return -1; } main() { int arr[10],i,pos,key; int startIndex=0; int endIndex=9; printf("enter the elements in array in sorted orderd only\n"); for(i=0;i<10;i++) { scanf("%d",&arr[i]); } printf("enter the element to be searched\n"); scanf("%d",&key); pos = binary_search(arr,key,startIndex,endIndex); if(pos!=-1) printf("element %d find at position %d",key,pos); else printf("element not in the array\n"); }

**Results:**

enter the elements in array in sorted orderd only

10

20

30

40

50

60

70

80

90

100

enter the element to be searched

20

element 20 find at position 1

enter the elements in array in sorted orderd only

10

20

30

40

50

60

70

80

90

100

enter the element to be searched

199

element not in the array

## No comments:

Post a Comment