Binary Search
Binary Search is a fundamental search algorithm used to find the position of a target element within a sorted array. It employs a divide-and-conquer strategy to efficiently narrow down the search space, making it significantly faster than linear search for larger datasets.
Problem Statement and Description
Given a sorted array and a target element, the problem is to determine whether the element exists in the array and, if so, return its index. Binary Search compares the target element with the middle element of the array, and based on the comparison result, halves the search space by discarding the half where the element cannot exist.
Example
Consider the sorted array: [-4, 2, 3, 7, 9, 12, 17, 19, 21]. Let's find the positions of a few elements using Binary Search:
- Target: 9 → Found at index 4
- Target: 2 → Found at index 1
- Target: 21 → Found at index 8
- Target: 11 → Not found
- Target: 3 → Found at index 2
Idea to Solve the Problem
Binary Search operates on the principle of narrowing down the search interval by half at each step. The steps are as follows:
- Find the middle element of the current search interval.
- Compare the middle element with the target element.
- If the middle element is equal to the target, return its index.
- If the middle element is greater than the target, narrow the interval to the lower half.
- If the middle element is less than the target, narrow the interval to the upper half.
- Repeat steps 1 to 5 until the interval becomes empty or the target is found.
Pseudocode
function find_node(arr, size, element)
i = 0, j = size - 1
while j >= i
mid = (i + j) / 2
if arr[mid] > element
j = mid - 1
else if arr[mid] < element
i = mid + 1
else
return mid
return -1Algorithm Explanation
The find_node function implements the Binary Search algorithm. It maintains two pointers,
i and j, representing the start and end of the current search interval. The
mid is calculated as the average of i and j. If the element at
mid is greater than the target, the search interval is narrowed to the lower half; if it's less,
the interval is narrowed to the upper half. If the element is found, its index is returned. If the interval
becomes empty, the element is not in the array.
Code Solution
// C Program
// Binary Search Algorithm
#include <stdio.h>
//Method which is finding given element index
int find_node(int arr[],int size,int element)
{
//Defining variables are control execution process of function
int i = 0, j = (size-1),mid=0;
//Two best case situation
if(arr[i]==element)
{
//when element is exist at first location
return i;
}
else if(arr[j]==element)
{
//when element is exist at last location
return j;
}
//Search intermediate element
while(j > i )
{
//Get middle element
mid = (i+j)/2;
if(arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid-1;
}
else if(arr[mid] < element)
{
//When middle element of index i and j are less
i = mid+1;
}
else
{
return mid;
}
}
return -1;
}
//Display the binary search operation result
void binary_search(int arr[],int size,int element)
{
if(size <= 0)
{
return;
}
int location = find_node(arr,size,element);
if(location==-1)
{
//When element are not exist
printf("\n %d are not exist", element);
}
else
{
//When resultant element is exist
printf("\n %d is at location [%d]", element, location);
}
}
//Print array element
void print_array(int arr[],int size)
{
printf("\n");
for(int i=0;i<size;i++)
{
printf(" %d ",arr[i] );
}
}
int main()
{
//Sorted array element
int arr[] = {-4, 2, 3, 7, 9, 12, 17, 19, 21};
//Get size of array
int size = sizeof(arr) / sizeof(arr[0]);
print_array(arr,size);
printf("\n---------------------");
//Test case
binary_search(arr,size,9);
binary_search(arr,size,2);
binary_search(arr,size,21);
binary_search(arr,size,11);
binary_search(arr,size,3);
return 0;
}
Output
-4 2 3 7 9 12 17 19 21
---------------------
9 is at location [4]
2 is at location [1]
21 is at location [8]
11 are not exist
3 is at location [2]//C++ Program
//Binary Search Algorithm
#include<iostream>
using namespace std;
class MyArray {
public:
void display(int arr[],int size) {
for (int i = 0; i < size; i++) {
cout << " " << arr[i];
}
}
//Method which is finding given element index
int find_node(int arr[], int size, int element) {
//Defining variables are control execution process of function
int i = 0, j = (size - 1), mid = 0;
//Two best case situation
if (arr[i] == element) {
return
//When element is exist at first location
i;
} else
if (arr[j] == element) {
return
//When element is exist at last location
j;
}
//Search intermediate element
while (j > i) {
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element) {
//When middle element of index i and j are greater
j = mid - 1;
} else
if (arr[mid] < element) {
//When middle element of index i and j are less
i = mid + 1;
} else {
return mid;
}
}
return -1;
}
//Display the binary search operation result
void binary_search(int arr[], int element,int size) {
if (size <= 0) {
return;
}
int location = this->find_node(arr, size, element);
if (location == -1) {
//When element are not exist
cout << "\n " << element << " are not exist";
} else {
//When resultant element is exist
cout << "\n " << element << " is at location [" << location << "]";
}
}
};
int main() {
MyArray obj = MyArray();
//Sorted array element
int arr[] = {
-4,
2,
3,
7,
9,
12,
17,
19,
21
};
int size = sizeof(arr)/sizeof(arr[0]);
obj.display(arr,size);
cout<<"\n---------------------"<<endl;
//Test case
obj.binary_search(arr, 9,size);
obj.binary_search(arr, 2,size);
obj.binary_search(arr, 21,size);
obj.binary_search(arr, 11,size);
obj.binary_search(arr, 3,size);
return 0;
}
Output
-4 2 3 7 9 12 17 19 21
---------------------
9 is at location [4]
2 is at location [1]
21 is at location [8]
11 are not exist
3 is at location [2]//Java Program
//Binary Search Algorithm
public class MyArray
{
public void display(int []arr)
{
for(int i = 0; i < arr.length; i++)
{
System.out.print(" "+arr[i]);
}
}
//Method which is finding given element index
public int find_node(int[] arr, int size, int element)
{
//Defining variables are control execution process of function
int i = 0, j = (size - 1), mid = 0;
//Two best case situation
if (arr[i] == element)
{
//When element is exist at first location
return i;
}
else if (arr[j] == element)
{
//When element is exist at last location
return j;
}
//Search intermediate element
while (j > i) {
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr[mid] < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
//Display the binary search operation result
public void binary_search(int[] arr, int element) {
int size = arr.length;
if (size <= 0) {
return;
}
int location = find_node(arr, size, element);
if (location == -1) {
//When element are not exist
System.out.print("\n "+element+" are not exist");
}
else
{
//When resultant element is exist
System.out.print("\n "+element+" is at location ["+location+"]");
}
}
public static void main(String[] args) {
MyArray obj = new MyArray();
//Sorted array element
int []arr = {-4, 2, 3, 7, 9, 12, 17, 19, 21};
obj.display(arr);
System.out.printf("\n---------------------");
//Test case
obj.binary_search(arr,9);
obj.binary_search(arr,2);
obj.binary_search(arr,21);
obj.binary_search(arr,11);
obj.binary_search(arr,3);
}
}
Output
-4 2 3 7 9 12 17 19 21
---------------------
9 is at location [4]
2 is at location [1]
21 is at location [8]
11 are not exist
3 is at location [2]//C# Program
//Binary Search Algorithm
using System;
public class MyArray {
public void display(int[] arr) {
for (int i = 0; i < arr.Length; i++) {
Console.Write(" " + arr[i]);
}
}
//Method which is finding given element index
public int find_node(int[] arr, int size, int element) {
//Defining variables are control execution process of function
int i = 0, j = (size - 1), mid = 0;
//Two best case situation
if (arr[i] == element) {
return i;
} else
if (arr[j] == element) {
return j;
}
//Search intermediate element
while (j > i) {
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element) {
//When middle element of index i and j are greater
j = mid - 1;
} else
if (arr[mid] < element) {
//When middle element of index i and j are less
i = mid + 1;
} else {
return mid;
}
}
return -1;
}
//Display the binary search operation result
public void binary_search(int[] arr, int element) {
int size = arr.Length;
if (size <= 0) {
return;
}
int location = find_node(arr, size, element);
if (location == -1) {
Console.Write("\n " + element + " are not exist");
} else {
Console.Write("\n " + element + " is at location [" + location + "]");
}
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
//Sorted array element
int[] arr = {
-4,
2,
3,
7,
9,
12,
17,
19,
21
};
obj.display(arr);
Console.Write("\n---------------------");
obj.binary_search(arr, 9);
obj.binary_search(arr, 2);
obj.binary_search(arr, 21);
obj.binary_search(arr, 11);
obj.binary_search(arr, 3);
}
}
Output
-4 2 3 7 9 12 17 19 21
---------------------
9 is at location [4]
2 is at location [1]
21 is at location [8]
11 are not exist
3 is at location [2]<?php
//Php Program
//Binary Search Algorithm
class MyArray {
public function display( $arr) {
for ($i = 0; $i < count($arr); $i++) {
echo(" ". $arr[$i]);
}
}
//Method which is finding given element index
public function find_node($arr, $size, $element) {
//Defining variables are control execution process of function
$i = 0;
$j = ($size - 1);
$mid = 0;
//Two best case situation
if ($arr[$i] == $element) {
return $i;
} else
if ($arr[$j] == $element) {
return $j;
}
//Search intermediate element
while ($j > $i) {
//Get middle element
$mid = intval(($i + $j) / 2);
if ($arr[$mid] > $element) {
//When middle element of index i and j are greater
$j = $mid - 1;
} else
if ($arr[$mid] < $element) {
//When middle element of index i and j are less
$i = $mid + 1;
} else {
return $mid;
}
}
return -1;
}
//Display the binary search operation result
public function binary_search( & $arr, $element) {
$size = count($arr);
if ($size <= 0) {
return;
}
$location = $this->find_node($arr, $size, $element);
if ($location == -1) {
//When element are not exist
echo("\n ". $element ." are not exist");
} else {
//When resultant element is exist
echo("\n ". $element ." is at location [". $location ."]");
}
}
}
function main() {
$obj = new MyArray();
//Sorted array element
$arr = array(-4, 2, 3, 7, 9, 12, 17, 19, 21);
$obj->display($arr);
printf("\n---------------------");
//Test case
$obj->binary_search($arr, 9);
$obj->binary_search($arr, 2);
$obj->binary_search($arr, 21);
$obj->binary_search($arr, 11);
$obj->binary_search($arr, 3);
}
main();
Output
-4 2 3 7 9 12 17 19 21
---------------------
9 is at location [4]
2 is at location [1]
21 is at location [8]
11 are not exist
3 is at location [2]//Node Js Program
//Binary Search Algorithm
class MyArray {
display(arr) {
for (var i = 0; i < arr.length; i++) {
process.stdout.write(" " + arr[i]);
}
}
//Method which is finding given element index
find_node(arr, size, element) {
//Defining variables are control execution process of function
var i = 0;
var j = (size - 1);
var mid = 0;
//Two best case situation
if (arr[i] == element) {
return i;
} else
if (arr[j] == element) {
return j;
}
//Search intermediate element
while (j > i) {
//Get middle element
mid = parseInt((i + j) / 2);
if (arr[mid] > element) {
//When middle element of index i and j are greater
j = mid - 1;
} else
if (arr[mid] < element) {
//When middle element of index i and j are less
i = mid + 1;
} else {
return mid;
}
}
return -1;
}
//Display the binary search operation result
binary_search(arr, element) {
var size = arr.length;
if (size <= 0) {
return;
}
var location = this.find_node(arr, size, element);
if (location == -1) {
//When element are not exist
process.stdout.write("\n " + element + " are not exist");
} else {
//When resultant element is exist
process.stdout.write("\n " + element + " is at location [" + location + "]");
}
}
}
function main(args) {
var obj = new MyArray();
//Sorted array element
var arr = [-4, 2, 3, 7, 9, 12, 17, 19, 21];
obj.display(arr);
process.stdout.write("\n---------------------");
//Test case
obj.binary_search(arr, 9);
obj.binary_search(arr, 2);
obj.binary_search(arr, 21);
obj.binary_search(arr, 11);
obj.binary_search(arr, 3);
}
main();
Output
-4 2 3 7 9 12 17 19 21
---------------------
9 is at location [4]
2 is at location [1]
21 is at location [8]
11 are not exist
3 is at location [2]# Python 3 Program
# Binary Search Algorithm
class MyArray :
def display(self, arr) :
i = 0
while (i < len(arr)) :
print(" ", arr[i], end = "")
i += 1
# Method which is finding given element index
def find_node(self, arr, size, element) :
i = 0
j = (size - 1)
mid = 0
# Two best case situation
if (arr[i] == element) :
return i
elif (arr[j] == element) :
return j
# Search intermediate element
while (j > i) :
# Get middle element
mid = int((i + j) / 2)
if (arr[mid] > element) :
# When middle element of index i and j are greater
j = mid - 1
elif (arr[mid] < element) :
# When middle element of index i and j are less
i = mid + 1
else :
return mid
return -1
# Display the binary search operation result
def binary_search(self, arr, element) :
size = len(arr)
if (size <= 0) :
return
location = self.find_node(arr, size, element)
if (location == -1) :
print("\n ", element ," are not exist", end = "")
else :
print("\n ", element ," is at location [", location ,"]", end = "")
def main() :
obj = MyArray()
arr = [-4, 2, 3, 7, 9, 12, 17, 19, 21]
obj.display(arr)
print("\n---------------------", end = "")
obj.binary_search(arr, 9)
obj.binary_search(arr, 2)
obj.binary_search(arr, 21)
obj.binary_search(arr, 11)
obj.binary_search(arr, 3)
if __name__ == "__main__":
main()
Output
-4 2 3 7 9 12 17 19 21
---------------------
9 is at location [ 4 ]
2 is at location [ 1 ]
21 is at location [ 8 ]
11 are not exist
3 is at location [ 2 ]# Ruby Program
# Binary Search Algorithm
class MyArray
def display(arr)
i = 0
while (i < arr.length)
print(" ", arr[i])
i += 1
end
end
# Method which is finding given element index
def find_node(arr, size, element)
i = 0
j = (size - 1)
mid = 0
# Two best case situation
if (arr[i] == element)
return i
elsif (arr[j] == element)
return j
end
# Search intermediate element
while (j > i)
# Get middle element
mid = (i + j) / 2
if (arr[mid] > element)
# When middle element of index i and j are greater
j = mid - 1
elsif (arr[mid] < element)
# When middle element of index i and j are less
i = mid + 1
else
return mid
end
end
return -1
end
# Display the binary search operation result
def binary_search(arr, element)
size = arr.length
if (size <= 0)
return
end
location = self.find_node(arr, size, element)
if (location == -1)
print("\n ", element ," are not exist")
else
print("\n ", element ," is at location [", location ,"]")
end
end
end
def main()
obj = MyArray.new()
arr = [-4, 2, 3, 7, 9, 12, 17, 19, 21]
obj.display(arr)
print("\n---------------------")
obj.binary_search(arr, 9)
obj.binary_search(arr, 2)
obj.binary_search(arr, 21)
obj.binary_search(arr, 11)
obj.binary_search(arr, 3)
end
main()
Output
-4 2 3 7 9 12 17 19 21
---------------------
9 is at location [4]
2 is at location [1]
21 is at location [8]
11 are not exist
3 is at location [2]//Scala Program
//Binary Search Algorithm
class MyArray {
def display(arr: Array[Int]): Unit = {
var i: Int = 0;
while (i < arr.length) {
print(" " + arr(i));
i += 1;
}
}
//Method which is finding given element index
def find_node(arr: Array[Int], size: Int, element: Int): Int = {
var i: Int = 0;
var j: Int = (size - 1);
var mid: Int = 0;
//Two best case situation
if (arr(i) == element) {
return i;
} else
if (arr(j) == element) {
return j;
}
//Search intermediate element
while (j > i) {
//Get middle element
mid = ((i + j) / 2).toInt;
if (arr(mid) > element) {
//When middle element of index i and j are greater
j = mid - 1;
} else
if (arr(mid) < element) {
//When middle element of index i and j are less
i = mid + 1;
} else {
return mid;
}
}
return -1;
}
//Display the binary search operation result
def binary_search(arr: Array[Int], element: Int): Unit = {
var size: Int = arr.length;
if (size <= 0) {
return;
}
val location: Int = find_node(arr, size, element);
if (location == -1) {
print("\n " + element + " are not exist");
} else {
print("\n " + element + " is at location [" + location + "]");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyArray = new MyArray();
val arr: Array[Int] = Array(-4, 2, 3, 7, 9, 12, 17, 19, 21);
obj.display(arr);
print("\n---------------------");
obj.binary_search(arr, 9);
obj.binary_search(arr, 2);
obj.binary_search(arr, 21);
obj.binary_search(arr, 11);
obj.binary_search(arr, 3);
}
}
Output
-4 2 3 7 9 12 17 19 21
---------------------
9 is at location [4]
2 is at location [1]
21 is at location [8]
11 are not exist
3 is at location [2]//Swift Program
//Binary Search Algorithm
class MyArray {
func display(_ arr: [Int]) {
var i: Int = 0;
while (i < arr.count) {
print(" ", arr[i], terminator: "");
i += 1;
}
}
//Method which is finding given element index
func find_node(_ arr: [Int], _ size: Int, _ element: Int) -> Int {
var i: Int = 0;
var j: Int = (size - 1);
var mid: Int = 0;
//Two best case situation
if (arr[i] == element) {
return i;
} else
if (arr[j] == element) {
return j;
}
//Search intermediate element
while (j > i) {
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element) {
//When middle element of index i and j are greater
j = mid - 1;
} else
if (arr[mid] < element) {
//When middle element of index i and j are less
i = mid + 1;
} else {
return mid;
}
}
return -1;
}
//Display the binary search operation result
func binary_search(_ arr: [Int], _ element: Int) {
let size: Int = arr.count;
if (size <= 0) {
return;
}
let location: Int = self.find_node(arr, size, element);
if (location == -1) {
print("\n ", element ," are not exist", terminator: "");
} else {
print("\n ", element ," is at location [", location ,"]", terminator: "");
}
}
}
func main() {
let obj: MyArray = MyArray();
let arr: [Int] = [-4, 2, 3, 7, 9, 12, 17, 19, 21];
obj.display(arr);
print("\n---------------------", terminator: "");
obj.binary_search(arr, 9);
obj.binary_search(arr, 2);
obj.binary_search(arr, 21);
obj.binary_search(arr, 11);
obj.binary_search(arr, 3);
}
main();
Output
-4 2 3 7 9 12 17 19 21
---------------------
9 is at location [ 4 ]
2 is at location [ 1 ]
21 is at location [ 8 ]
11 are not exist
3 is at location [ 2 ]// Rust Program
// Binary Search Algorithm
fn main() {
//Sorted array element
let arr : [i32;9] =[-4,2,3,7,9,12,17,19,21];
//Get size of array
let size : usize = arr.len();
print_array(&arr, size);
print!("\n---------------------");
//Test case
binary_search(&arr, size, 9);
binary_search(&arr, size, 2);
binary_search(&arr, size, 21);
binary_search(&arr, size, 11);
binary_search(&arr, size, 3);
}
fn print_array(arr: &[i32], size: usize) {
print!("\n");
let mut i: usize = 0;
while i < size {
print!(" {} ", arr[i]);
i += 1;
}
}
fn binary_search(arr: &[i32], size: usize, element: i32) {
if size <= 0 {
return;
}
let location: i32 = find_node(arr, size, element);
if location == -1 {
//When element are not exist
print!("\n {} are not exist", element);
}
else {
//When resultant element is exist
print!("\n {} is at location [{}]", element, location);
}
}
fn find_node(arr: &[i32], size: usize, element: i32) -> i32 {
//Defining variables are control execution process of function
let mut i: usize = 0;
let mut j: usize = size - 1;
let mut mid;
//Two best case situation
if arr[i] == element {
//when element is exist at first location
return i as i32;
}
else
if arr[j] == element {
//when element is exist at last location
return j as i32;
}
//Search intermediate element
while j > i {
//Get middle element
mid = (i + j) / 2;
if arr[mid] > element {
//When middle element of index i and j are greater
j = mid - 1;
}
else
if arr[mid] < element {
//When middle element of index i and j are less
i = mid + 1;
}
else {
return mid as i32;
}
}
return -1;
}
Output
-4 2 3 7 9 12 17 19 21
---------------------
9 is at location [4]
2 is at location [1]
21 is at location [8]
11 are not exist
3 is at location [2]Time Complexity
Binary Search has a time complexity of O(log n), where n is the number of elements in the array. This efficiency comes from halving the search interval in each step, allowing it to quickly converge to the target.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment