In computer science, a

**binary search**or**half-interval search**algorithm finds the position of a specified value (the input "key") within a sorted array. In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special "Not found" indication is returned.
A binary search halves the number of items to check with each iteration, so locating an item (or determining its absence) takes logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.

###
*Algorithm/Pseudo-code:*

*Algorithm/Pseudo-code:*

###
__Recursive Algorithm__

__Recursive Algorithm__

A straightforward implementation of binary search is recursive. The initial call uses the indices of the entire array to be searched. The procedure then calculates an index midway between the two indices, determines which of the two subarrays to search, and then does a recursive call to search that subarray.

Each of the calls is tail recursive, so a compiler need not make a new stack frame for each call. The variables `imin`

and `imax`

are the lowest and highest inclusive indices that are searched.int binary_search(int A[], int key, int imin, int imax) { // test if array is empty if (imax < imin): // set is empty, so return value showing not found return KEY_NOT_FOUND; else { // calculate midpoint to cut set in half int imid = midpoint(imin, imax); // three-way comparison if (A[imid] > key) // key is in lower subset return binary_search(A, key, imin, imid-1); else if (A[imid] < key) // key is in upper subset return binary_search(A, key, imid+1, imax); else // key has been found return imid; } }

```
```

It is invoked with initial

`imin`

and `imax`

values of `0`

and `N-1`

for a zero based array.
The number type "int" shown in the code has an influence on how the midpoint calculation can be implemented correctly. With unlimited numbers, the midpoint can be calculated as

`"(imin + imax) / 2"`

###
*C Code For Binary Search:*

*C Code For Binary Search:*

/* Double-Click To Select Code */ #include<stdio.h> #include<conio.h> void main() { int arr[10], num, i, n, found=0, pos=-1, beg, end, mid; clrscr(); printf("Enter the number of elements in the array: "); scanf("%d",&n); printf("\nEnter the elements: \n"); for(i=0 ; i < n ; i++) { printf("arr[%d] = ",i); scanf("%d",&arr[i]); } printf("\nEnter the number that has to be searched: "); scanf("%d",&num); beg=0; end=n-1; while(beg<=end) { mid=(beg end)/2; if(arr[mid]==num) { printf("\n %d is present in the array at position = %d",num,mid); found=1; break; } if(arr[mid] > num) end = mid-1; else if(arr[mid] < num) beg = mid+1; } if(beg > end && found==0) printf("\n %d does not exist in the array",num); getch(); }

This Code Is Quite Easy. First we take the no. of elements from the user and then user enter them. Then user inputs the element that has to be searched. Then we begin the searching. If the element to be found is the middle element, the element is shown, other wise for the two conditions, arr[mid] > num or arr[mid] < num, the search iterates, either till the element is found or until the array gets terminated.

###
*Output:*

*Output:*

This article uses material from the Wikipedia article Binary search algorithm which is released under the Creative Commons Attribution-Share-Alike License 3.0

Do you like this post? Please link back to this article by copying one of the codes below.

URL: HTML link code: Forum link code: