Q. Write an algorithm and program of binary search.

Binary Search :- Binary search is a fast search algorithm with run-time complexity of search O(log n). For this algorithm to work properly, elements must be in a sorted form.

Binary Search Algorithm

START
do until the pointers low and high meet each other.
mid = (low + high)/2
if (x == arr[mid])
return mid
else if (x > A[mid]) // x is on the right side
low = mid + 1
else                       // x is on the left side
high = mid - 1
STOP

Binary Search Program

C++

Java

Python

PHP

// Binary Search in C
#include <stdio.h>
int binary_search(int array[], int num, int low, int high)
{
while (low <= high)
{
int mid = low + (high - low) / 2;
if (array[mid] == num)
return mid;
if (array[mid] < num)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main(void)
{
int array[] = {10, 20, 30, 40, 50, 60, 70, 80};
int len = sizeof(array) / sizeof(array[0]);
int num = 40;
int res = binary_search(array, num, 0, len - 1);
if (res == -1)
printf("Element Not found");
else
printf("Element is found at index %d", res);
return 0;
}

// Binary Search in C++
#include <iostream>
using namespace std;
int binary_search(int array[], int num, int low, int high)
{
while (low <= high)
{
int mid = low + (high - low) / 2;
if (array[mid] == num)
return mid;
if (array[mid] < num)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main(void)
{
int array[] = {10, 20, 30, 40, 50, 60, 70, 80};
int len = sizeof(array) / sizeof(array[0]);
int num = 40;
int res = binary_search(array, num, 0, len - 1);
if (res == -1)
cout<<"Element Not found";
else
cout<<"Element is found at index "<< res;
return 0;
}

// Binary Search in Java
class LFC {
int binary_search(int array[], int num, int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == num)
return mid;
if (array[mid] < num)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
public static void main(String args[]) {
LFC ob = new LFC();
int array[] = { 10, 20, 30, 40, 50, 60, 70, 80 };
int len = array.length;
int num = 40;
int result = ob.binary_search(array, num, 0, len - 1);
if (result == -1)
System.out.println("Element Not Found");
else
System.out.println("Element is found at index " + result);
}
}

# Binary Search in python
def binary_search (array, num, low, high): 
while low <= high: 
mid = low + (high - low)//2
if array[mid] == num: 
return mid 
elif array[mid] < num: 
low = mid + 1
else: 
high = mid - 1
return -1
array = [ 10, 20, 30, 40, 50, 60, 70, 80 ] 
num = 40
result = binary_search(array, num, 0, len(array)-1) 
if result != -1: 
print("Element is found at index " + str(result))
else: 
print("Element Not found")

using System;
namespace LFC
{
class LFC
{
public static void Main()
{
int num=40,len=8;
int []a ={10, 20, 30, 40, 50, 60, 70, 80};
int low = 0;
int high = len - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (num < a[mid])
high = mid - 1;
else if (num > a[mid])
low = mid + 1;
else if (num == a[mid])
{
Console.WriteLine("Element is found at index {0}\n", mid);
return;
}
}
Console.WriteLine("Element Not Found");
}
}
}

function binary_search(Array $arr, $x) 
{ 
if (count($arr) === 0) return false; 
$low = 0; 
$high = count($arr) - 1; 
while ($low <= $high) { 
$mid = floor(($low + $high) / 2); 
if($arr[$mid] == $x) { 
return $mid; 
} 
if ($x < $arr[$mid]) { 
$high = $mid -1; 
} 
else { 
$low = $mid + 1; 
} 
} 
return -1; 
} 
// Driver code 
$arr = array(10, 20, 30, 40, 50, 60, 70, 80); 
$value = 40; 
$val=binary_search($arr, $value);
if($val>=0) { 
echo "Element is found at index $val"; 
} 
else { 
echo "Element Not Found"; 
}

// Binary Search in C
#include <stdio.h>
int binarySearch(int array[], int num, int low, int high)
{
while (low <= high)
{
int mid = low + (high - low) / 2;
if (array[mid] == num)
return mid;
if (array[mid] < num)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main(void)
{
int array[] = {10, 20, 30, 40, 50, 60, 70, 80};
int len = sizeof(array) / sizeof(array[0]);
int num = 40;
int res = binarySearch(array, num, 0, len - 1);
if (res == -1)
printf("Element Not Found");
else
printf("Element is found at index %d", res);
return 0;
}

Output

Element is found at index 3

Recommended Programs

Bubble sort program (Descending Order)
Bubble sort program (Ascending Order)