In Data Structure and Algorithm, Binary Search is a searching mechanism that is implemented to search an element from an array. Binary search always works on a sorted array (ascending/descending). In each step of Binary Search, we split every section into two sub-sections based on mid of the section.
1. Left side sub-section of Mid.
2. Right side sub-section of Mid.
If the element is found at the mid-position of the section, then we can conclude that the searching element is found. But in the case of an ascending order sorted array, if the searching element is lesser than mid-value, then we will search the element in the left sub-section of the mid, if the searching element is greater than mid-value, then we will search an element in the right sub-section of the mid. This divide and conquer approach will be continued either until the element is found or until there is no dividing option is left.
Similarly, in the case of a descending order sorted array, if the searching element is lesser than mid-value, then we will search an element in the right sub-section of the mid, if the searching element is greater than mid-value, then we will search an element in the left sub-section of the mid. This divide and conquer approach will be continued either until the element is found or until there is no dividing option is left.
Basic Understanding of Binary Search
Step 1: Start
Step 2: Take input for the number of elements (size) you want to insert with in array
Step 3: Take the elements with in the array (array).
Step 4: Take the element (search) that you what to search with in the array.
Step 5: Set start = 0
Step 6: Set end = size - 1
Step 7: Set mid = (start+end)/2
Step 8: While (start <= end)
If (array[mid] == search)
Print "Value Found"
break
Else If (array[mid] < search)
first = mid + 1;
Else
last = mid - 1;
End IF
mid = (start + end)/2;
End While
Step 9: If (start > end)
Print "Not Found"
End If
Step 10: StopHow exactly it works?
Here, we have an array of 5 elements. All the elements within the array remain in ascending order. We have to check if 20 exists within this array or not?
Now, we will set the value of Start with the starting index value that is 0 and set the value of End with the value size-1. The set the mid-value = (Start + End)/2
Here, we have checked the array[mid] = 20 or not. It is clear to us that array[mid] is greater than 20, so we have to check the left subsection. We have shifted End at mid-1.
We have calculated the mid again. Now mid=(0+1)/2=0. 20 is not present at array[mid] which means array[0] and 20 is greater than array[0] so, the element is the right subsection.
So, now we need to shift the Start at mid+1. Hence, Start is at array[1]
Again, calculate mid. mid = (Start + End)/2 , that is mid=1. Now check if array[1]=20 or not? Yes, array[1]=20. So, we can conclude element is found.
Implementation of Binary Search in C
#include <stdio.h>
int main()
{
int index, start, end, mid, size, search, array[100];
printf("Enter the number of elements\n");
scanf("%d",&size);
//Solution at codeWindow.in
printf("Enter %d integers\n", size);
for (index = 0; index < size; index++)
scanf("%d",&array[index]);
printf("Enter the value to find\n");
scanf("%d", &search);
start = 0;
end = size - 1;
mid = (start+end)/2;
while (start <= end)
{
if (array[mid] == search)
{
printf("%d found at location %d.\n", search, mid+1);
break;
}
else if (array[mid] < search)
start = mid + 1;
else
end = mid - 1;
mid = (start + end)/2;
}
if (start > end)
printf("Not found! %d isn't present in the list.\n", search);
//Solution at codeWindow.in
return 0;
}Input:
Enter the number of elements 5
Enter 5 integers
10 20 30 40 50
Enter the value to find
20
Output:
20 found at location 2.
You may read
You may read
Implementation of Binary Search in JAVA
import java.util.*;
import java.lang.*;
import java.io.*;
class CodeWindow
{
public static void main (String[] args) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the number of elements ");
int size = Integer.parseInt(br.readLine());
System.out.println("Enter " + size + " integers ");
String str[] = br.readLine().split(" ");
int array[] = new int[size];
for(int index=0; index<size; index++)
array[index] = Integer.parseInt(str[index]);
System.out.println("Enter the value to find ");
int search = Integer.parseInt(br.readLine());
int start = 0;
int end = size - 1;
int mid = (start + end) / 2;
while (start <= end)
{
if (array[mid] == search)
{
System.out.println(search + " found at location " + (mid+1) + ".");
break;
}
else if (array[mid] < search)
start = mid + 1;
else
end = mid - 1;
mid = (start + end)/2;
}
if (start > end)
System.out.println("Not found! " + search + " isn't present in the list.");
}
}
Input:
Enter the number of elements 5
Enter 5 integers
10 20 30 40 50
Enter the value to find
20
Output:
20 found at location 2.
Analysis of Binary Search
The time complexity of binary search in all three cases is given below
Best Case: The best case complexity is O(1). i.e. if the element to search is the middle element of the complete array. There needs only one comparison.
Average Case: Binary search is applied here using the divide and conquer approach. The search cut the range in half every time.
