## 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
• C++
• Java
• Python
• C#
• 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)