Q27. Write a code to search element in array using binary search algorithm
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 Tree 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
Code Binary Search Tree
#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[] = {5,8,7,6,9,10};
int len = sizeof(array) / sizeof(array[0]);
int num = 6;
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;
}
#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[] = {5,8,7,6,9,10};
int len = sizeof(array) / sizeof(array[0]);
int num = 6;
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;
}
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[] = {5,8,7,6,9,10};
int len = array.length;
int num = 6;
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);
}
}
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 = [ 5,8,7,6,9,10 ]
num = 6
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”)
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(5,8,7,6,9,10);
$value = 6;
$val=binary_search($arr, $value);
if($val>=0) {
echo “Element is found at index $val”;
}
else {
echo “Element Not Found”;
}
Output
Element is found at index 3
Recommended Programs
Program to find factorial of a number
Program to count number of digits in a number