Summary: In this tutorial, we will learn what is the Binary Search algorithm and how to use the Binary Search algorithm to search an element in an array.
Introduction to Binary Search Algorithm
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.
https://en.wikipedia.org/wiki/Binary_search_algorithm
Binary Search is a Divide and Conquer algorithm that is used to search an element in a linear data structure (such as an array, a linked list, etc).
It compares the search element with the middle element of the array.
If they are not equal, the algorithm looks for the search element into either half of the array.
After every unmatched comparison, the algorithm eliminates the half in which the search element cannot lie.
For example, consider the following array:
The array is sorted in ascending order and the target element is 9.
Binary search will first compare 9 with the middle element of the array i.e. 3.
Because the middle element is 3 which is less than 9 and the array is in ascending order, the binary search algorithm eliminates the first half of the array knowing 9 cannot lie in the first half.
Again the algorithm compares 9 with the middle element of the second half i.e. 7. Results in no match. Knowing 9 is greater than 7, it eliminates the first of the partitioned array.
In the next round, the algorithm compares the target element with the only left element i.e. 9, and the match is found.
Steps for Binary Search in Programming
- Initialize the array with values.
- Sort the array in ascending order.
- Compare the search element with the middle element of the array. If
searchElement > array[mid]then step 4, else ifsearchElement<array[mid]then step 5, else ifsearchElement==array[mid]then step 6. - Eliminate the first half of the array (i.e.
start=mid+1)and repeat step 3 for the second half. - Eliminate the second half (i.e.
end=mid-1) and repeat step 3 for the first half. - Output “Found” and End.
- If the array index goes out of bounds i.e.
start>endthen it means the search element is not present in the array. Output “Not Found” and End.
Here is the implementation of the steps in C and Java.
C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int main()
{
int array[] = {9, 2 ,6, -5, 3 , 0, 7};
int start, mid, end, searchElement;
bool flag = false;
printf("Enter a number to begin search using Binary Search:\n");
scanf("%d",&searchElement);
//Calculating the size of the array
int sizeOfArray = sizeof(array)/sizeof(array[0]);
//Sorting the array
sort(array, sizeOfArray);
start = 0;
end = sizeOfArray - 1;
while(start<= end){
mid = (start + end) /2;
if(array[mid] == searchElement){
printf("YES %d is present in the array \n",searchElement);
flag = true; //Means Found
break; //Breaking out of loop because no more search operation required
}
else if (array[mid] < searchElement){
start = mid+1;
}
else {
end = mid-1;
}
}
if(!flag) //Means flag == false
printf("Search Element not Found \n");
return 0;
}
void sort(int array[], int sizeOfArray){
int i,j, temp;
//Sorting array using bubble sort
for(i=0; i< sizeOfArray - 1; i++){
for(j=0; j<sizeOfArray-i-1; j++){
if(array[j] > array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}Java
import java.util.Scanner;
public class App {
static Scanner in= new Scanner(System.in);
public static void main(String args[]){
int array[] = {9, 2 ,6, -5, 3 , 0, 7};
int start, mid, end, searchElement;
boolean flag = false;
System.out.println("Enter a number to begin search using Binary Search:");
searchElement = in.nextInt();
//Sorting the array
sort(array, array.length);
start = 0;
end = array.length - 1;
while(start<= end){
mid = (start + end) /2;
if(array[mid] == searchElement){
System.out.println("YES "+ searchElement+" is present in the array ");
flag = true; //Means Found
break; //Breaking out of loop because no more search operation required
}
else if (array[mid] < searchElement){
start = mid+1;
}
else {
end = mid-1;
}
}
if(!flag) //Means flag == false
System.out.println("Search Element not Found ");
}
private static void sort(int[] array, int size){
int i,j, temp;
//Sorting array using bubble sort
for(i=0; i< size - 1; i++){
for(j=0; j<size-i-1; j++){
if(array[j] > array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}Output
In this tutorial, we learned what is Binary Search Algorithm and how to implement binary search algorithm in C and Java.