Scribd
Upload
19 views18 pages

Binary Search - Javatpoint

The document provides an overview of the Binary Search Algorithm, which is an efficient searching technique for sorted lists that utilizes a divide and conquer approach. It includes the algorithm's steps, time and space complexity analysis, and implementation examples in various programming languages such as C, C++, C#, Java, and PHP. The best-case time complexity is O(1), while the average and worst-case complexities are O(logn), with a space complexity of O(1).

Uploaded by

emilratiu00
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views18 pages

Binary Search - Javatpoint

The document provides an overview of the Binary Search Algorithm, which is an efficient searching technique for sorted lists that utilizes a divide and conquer approach. It includes the algorithm's steps, time and space complexity analysis, and implementation examples in various programming languages such as C, C++, C#, Java, and PHP. The best-case time complexity is O(1), while the average and worst-case complexities are O(logn), with a space complexity of O(1).

Uploaded by

emilratiu00
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 18

1/20/25, 9:02 PM Binary Search - javatpoint


Home Python Java JavaScript HTML SQL PHP C#

DS Tutorial

DS Tutorial

DS Introduction

DS Algorithm

Asymptotic Analysis

DS Pointer

DS Structure

DS Array

DS Array

2D Array

DS Linked List

Linked List

Types of Linked List

Singly Linked List

Doubly Linked List

Circular Linked List

Circular Doubly List

https://www.javatpoint.com/binary-search 1/18
1/20/25, 9:02 PM Binary Search - javatpoint

Skip list in DS

DS Stack

DS Stack

Array Implementation

← prev next →

Binary Search Algorithm


In this article, we will discuss the Binary Search Algorithm. Searching is the process of
finding some particular element in the list. If the element is present in the list, then the
process is called successful, and the process returns the location of that element.
Otherwise, the search is called unsuccessful.

Linear Search and Binary Search are the two popular searching techniques. Here we will
discuss the Binary Search Algorithm.

Binary search is the search technique that works efficiently on sorted lists. Hence, to search
an element into some list using the binary search technique, we must ensure that the list is
sorted.

Binary search follows the divide and conquer approach in which the list is divided into two
halves, and the item is compared with the middle element of the list. If the match is found
then, the location of the middle element is returned. Otherwise, we search into either of the
halves depending upon the result produced through the match.

NOTE: Binary search can be implemented on sorted array elements. If the list
elements are not arranged in a sorted manner, we have first to sort them.

Now, let's see the algorithm of Binary Search.

Algorithm

https://www.javatpoint.com/binary-search 2/18
1/20/25, 9:02 PM Binary Search - javatpoint

Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bo


und' is the index of the first array element, 'upper_bound' is the index of the last ar
ray element, 'val' is the value to search
Step 1: set beg = lower_bound, end = upper_bound, pos = - 1
Step 2: repeat steps 3 and 4 while beg <=end
Step 3: set mid = (beg + end)/2
Step 4: if a[mid] = val
set pos = mid
print pos
go to step 6
else if a[mid] > val
set end = mid - 1
else
set beg = mid + 1
[end of if]
[end of loop]
Step 5: if pos = -1
print "value is not present in the array"
[end of if]
Step 6: exit

Working of Binary search


Now, let's see the working of the Binary Search Algorithm.

To understand the working of the Binary search algorithm, let's take a sorted array. It will be
easy to understand the working of Binary search with an example.

There are two methods to implement the binary search algorithm -

Iterative method

Recursive method

The recursive method of binary search follows the divide and conquer approach.

Let the elements of array are -

https://www.javatpoint.com/binary-search 3/18
1/20/25, 9:02 PM Binary Search - javatpoint

Let the element to search is, K = 56

We have to use the below formula to calculate the mid of the array -

mid = (beg + end)/2

So, in the given array -

beg = 0

end = 8

mid = (0 + 8)/2 = 4. So, 4 is the mid of the array.

https://www.javatpoint.com/binary-search 4/18
1/20/25, 9:02 PM Binary Search - javatpoint

Now, the element to search is found. So algorithm will return the index of the element
matched.

Binary Search complexity


Now, let's see the time complexity of Binary search in the best case, average case, and worst
case. We will also see the space complexity of Binary search.

1. Time Complexity

Case Time Complexity

Best Case O(1)

Average Case O(logn)

Worst Case O(logn)

Best Case Complexity - In Binary search, best case occurs when the element to
search is found in first comparison, i.e., when the first middle element itself is the
element to be searched. The best-case time complexity of Binary search is O(1).

Average Case Complexity - The average case time complexity of Binary search is
O(logn).

Worst Case Complexity - In Binary search, the worst case occurs, when we have
to keep reducing the search space till it has only one element. The worst-case
time complexity of Binary search is O(logn).

2. Space Complexity

Space Complexity O(1)

https://www.javatpoint.com/binary-search 5/18
1/20/25, 9:02 PM Binary Search - javatpoint

The space complexity of binary search is O(1).

Implementation of Binary Search


Now, let's see the programs of Binary search in different programming languages.

Program: Write a program to implement Binary search in C language.

#include <stdio.h>
int binarySearch(int a[], int beg, int end, int val)
{
int mid;
if(end >= beg)
{ mid = (beg + end)/2;
/* if the item to be searched is present at middle */
if(a[mid] == val)
{
return mid+1;
}
/* if the item to be searched is smaller than middle, then it can only be in left s
ubarray */
else if(a[mid] < val)
{
return binarySearch(a, mid+1, end, val);
}
/* if the item to be searched is greater than middle, then it can only be in right
subarray */
else
{
return binarySearch(a, beg, mid-1, val);
}
}
return -1;
}
int main() {
int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70}; // given array
int val = 40; // value to be searched

https://www.javatpoint.com/binary-search 6/18
1/20/25, 9:02 PM Binary Search - javatpoint

int n = sizeof(a) / sizeof(a[0]); // size of array


int res = binarySearch(a, 0, n-1, val); // Store result
printf("The elements of the array are - ");
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\nElement to be searched is - %d", val);
if (res == -1)
printf("\nElement is not present in the array");
else
printf("\nElement is present at %d position of array", res);
return 0;
}

Output

Program: Write a program to implement Binary search in C++.

#include <iostream>
using namespace std;
int binarySearch(int a[], int beg, int end, int val)
{
int mid;
if(end >= beg)
{
mid = (beg + end)/2;
/* if the item to be searched is present at middle */
if(a[mid] == val)
{
return mid+1;
}
/* if the item to be searched is smaller than middle, then it can only be in left s
ubarray */
else if(a[mid] < val)
{
return binarySearch(a, mid+1, end, val);

https://www.javatpoint.com/binary-search 7/18
1/20/25, 9:02 PM Binary Search - javatpoint

}
/* if the item to be searched is greater than middle, then it can only be in right s
ubarray */
else
{
return binarySearch(a, beg, mid-1, val);
}
}
return -1;
}
int main() {
int a[] = {10, 12, 24, 29, 39, 40, 51, 56, 70}; // given array
int val = 51; // value to be searched
int n = sizeof(a) / sizeof(a[0]); // size of array
int res = binarySearch(a, 0, n-1, val); // Store result
cout<<"The elements of the array are - ";
for (int i = 0; i < n; i++)
cout<<a[i]<<" ";
cout<<"\nElement to be searched is - "<<val;
if (res == -1)
cout<<"\nElement is not present in the array";
else
cout<<"\nElement is present at "<<res<<" position of array";
return 0;
}

Output

Program: Write a program to implement Binary search in C#.

using System;
class BinarySearch {
static int binarySearch(int[] a, int beg, int end, int val)
{
int mid;

https://www.javatpoint.com/binary-search 8/18
1/20/25, 9:02 PM Binary Search - javatpoint

if(end >= beg)


{
mid = (beg + end)/2;
if(a[mid] == val)
{
return mid+1; /* if the item to be searched is present at middle */
}
/* if the item to be searched is smaller than middle, then it can only be in left s
ubarray */
else if(a[mid] < val)
{
return binarySearch(a, mid+1, end, val);
}
/* if the item to be searched is greater than middle, then it can only be in right
subarray */
else
{
return binarySearch(a, beg, mid-1, val);
}
}
return -1;
}
static void Main() {
int[] a = {9, 11, 23, 28, 38, 45, 50, 56, 70}; // given array
int val = 70; // value to be searched
int n = a.Length; // size of array
int res = binarySearch(a, 0, n-1, val); // Store result
Console.Write("The elements of the array are - ");
for (int i = 0; i < n; i++)
{
Console.Write(a[i] + " ");
}
Console.WriteLine();
Console.WriteLine("Element to be searched is - " + val);
if (res == -1)
Console.WriteLine("Element is not present in the array");
else

https://www.javatpoint.com/binary-search 9/18
1/20/25, 9:02 PM Binary Search - javatpoint

Console.WriteLine("Element is present at " + res + " position of array");


}
}

Output

Program: Write a program to implement Binary search in Java.

class BinarySearch {
static int binarySearch(int a[], int beg, int end, int val)
{
int mid;
if(end >= beg)
{
mid = (beg + end)/2;
if(a[mid] == val)
{
return mid+1; /* if the item to be searched is present at middle
*/
}
/* if the item to be searched is smaller than middle, then it can only
be in left subarray */
else if(a[mid] < val)
{
return binarySearch(a, mid+1, end, val);
}
/* if the item to be searched is greater than middle, then it can only be
in right subarray */
else
{
return binarySearch(a, beg, mid-1, val);
}
}
return -1;
}
https://www.javatpoint.com/binary-search 10/18
1/20/25, 9:02 PM Binary Search - javatpoint

public static void main(String args[]) {


int a[] = {8, 10, 22, 27, 37, 44, 49, 55, 69}; // given array
int val = 37; // value to be searched
int n = a.length; // size of array
int res = binarySearch(a, 0, n-1, val); // Store result
System.out.print("The elements of the array are: ");
for (int i = 0; i < n; i++)
{
System.out.print(a[i] + " ");
}
System.out.println();
System.out.println("Element to be searched is: " + val);
if (res == -1)
System.out.println("Element is not present in the array");
else
System.out.println("Element is present at " + res + " position of array");
}
}

Output

Program: Write a program to implement Binary search in PHP.

<?php
function binarySearch($a, $beg, $end, $val)
{
if($end >= $beg)
{
$mid = floor(($beg + $end)/2);
if($a[$mid] == $val)
{
return $mid+1; /* if the item to be searched is present at middle */
}

https://www.javatpoint.com/binary-search 11/18
1/20/25, 9:02 PM Binary Search - javatpoint

/* if the item to be searched is smaller than middle, then it can only be in left su
barray */
else if($a[$mid] < $val)
{
return binarySearch($a, $mid+1, $end, $val);
}
/* if the item to be searched is greater than middle, then it can only be in right s
ubarray */
else
{
return binarySearch($a, $beg, $mid-1, $val);
}
}
return -1;
}
$a = array(7, 9, 21, 26, 36, 43, 48, 54, 68); // given array
$val = 68; // value to be searched
$n = sizeof($a); // size of array
$res = binarySearch($a, 0, $n-1, $val); // Store result
echo "The elements of the array are: ";
for ($i = 0; $i < $n; $i++)
echo " " , $a[$i];
echo "<br>" , "Element to be searched is: " , $val;
if ($res == -1)
echo "<br>" , "Element is not present in the array";
else
echo "<br>" , "Element is present at " , $res , " position of array";
?>

Output

So, that's all about the article. Hope the article will be helpful and informative to you.

https://www.javatpoint.com/binary-search 12/18
1/20/25, 9:02 PM Binary Search - javatpoint

Next Topic Bubble sort

← prev next →

Related Posts

Linear Search
Algorithm In this article, we will discuss the Algorithm. Searching is the process of finding
some particular element in the list. If the element is present in the list, then the process is
called successful, and the process returns the location of that element; otherwise,...

 7 min read

Learn Important Tutorial

Python Java

Javascript HTML

https://www.javatpoint.com/binary-search 13/18
1/20/25, 9:02 PM Binary Search - javatpoint

Database PHP

C++ React

B.Tech / MCA

Data
DBMS
Structures

Operating
DAA
System

Computer Compiler
Network Design

https://www.javatpoint.com/binary-search 14/18
1/20/25, 9:02 PM Binary Search - javatpoint

Computer Discrete
Organization Mathematics

Ethical Computer
Hacking Graphics

Web Software
Technology Engineering

Cyber
Automata
Security

C
C++
Programming

Java .Net

https://www.javatpoint.com/binary-search 15/18
1/20/25, 9:02 PM Binary Search - javatpoint

Python Programs

Control Data
System Warehouse

Preparation

Aptitude Reasoning

Verbal Interview
Ability Questions

https://www.javatpoint.com/binary-search 16/18
1/20/25, 9:02 PM Binary Search - javatpoint

Company
Questions

https://www.javatpoint.com/binary-search 17/18
1/20/25, 9:02 PM Binary Search - javatpoint

https://www.javatpoint.com/binary-search 18/18

You might also like