Binary Search
Binary search is technique which are find the element index in sorted array. That is an effective mechanism which to get element position in minimum comparison.
Here given code implementation process.
// 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]
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