In Progress
Lesson 7, Topic 2
In Progress

# Binary Search

Lesson Progress
0% Complete

Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.

Binary search looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the subarray reduces to zero.

## Binary Search Algorithm

• Step 1: [INITIALIZE] SET BEG = lower_bound
END = upper_bound, POS = – 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 POS = MID
PRINT POS
Go to Step 6
ELSE IF A[MID] > VAL
SET END = MID – 1
ELSE
SET BEG = MID + 1
[END OF IF]
[END OF LOOP]
• Step 5: IF POS = -1
PRINT “VALUE IS NOT PRESENT IN THE ARRAY”
[END OF IF]
• Step 6: EXIT

## Complexity

### Example :

Let us consider an array arr = {1, 5, 7, 8, 13, 19, 20, 23, 29}. Find the location of the item 23 in the array.

In First step :

1. BEG = 0
2. END = 8
3. MID = 4
4. a[mid] = a = 13 < 23, therefore

In Second step:

1. Beg = mid +1 = 5
2. End = 8
3. mid = 13/2 = 6
4. a[mid] = a = 20 < 23, therefore;

In Third step:

1. beg = mid + 1 = 7
2. End = 8
3. mid = 15/2 = 7
4. a[mid] = a
5.  a = 23 = item;
6. therefore, set location = mid;
7. The location of the item will be 7.

## Binary Search Program using Recursion

### C program

``````#include<stdio.h>
int binarySearch(int[], int, int, int);
void main ()
{
int arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};
int item, location=-1;
printf("Enter the item which you want to search ");
scanf("%d",&item);
location = binarySearch(arr, 0, 9, item);
if(location != -1)
{
printf("Item found at location %d",location);
}
else
{
}
}
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 item which you want to search19Item found at location 2`

## Binary Search function using Iteration

``````int binarySearch(int a[], int beg, int end, int item)
{
int mid;
while(end >= beg)
{
mid = (beg + end)/2;
if(a[mid] == item)
{
return mid+1;
}
else if(a[mid] < item)
{
beg = mid + 1;
}
else
{
end = mid - 1;
}
}
return -1;
}   ``````