Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
C++ Code for Binary Search
3.
Inbuilt Binary Search in C++
4.
Inbuilt Binary Search in Java
5.
Frequently Asked Questions
5.1.
What is the time and space complexity of the Binary Search algorithm?
5.2.
Is it necessary to have sorted data using a binary search algorithm?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Inbuilt Binary Search in Different Languages

Author Riya
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

This blog will discuss binary search and various inbuilt library functions to do a binary search in different languages. Before jumping into the discussion of binary search, let's first recall what is searching and what is linear search.

 

Searching is a technique to find whether the given element exists or not in a given array, and if it exists, then what is its position? Binary search is a technique for searching an element in a sorted array.

Also see, Introduction to Binary Search Tree

Let's assume an array of integers:

arr= [1, 7, 6, 8, 9, 4], and we have to find if “8” exists in the array or not, and if it exists, we have to find its position in the array. 

The linear search technique is to traverse the whole array linearly and check if the current element equals the given element. If it is equal to the given element, return its position, and move to the next position. After traversing the array, return that the element doesn't exist if the element is not found.

The time complexity of this algorithm is O(N), where 'N' is the number of elements in the given array.

How do we reduce the time complexity or say how to perform the searching operation in less time.

We can reduce the time complexity of searching in a sorted array by using binary search. Let's assume that we have an array sorted in increasing order, and we have to do a binary search in it for a given element. We divide the array into two parts in binary search and compare the given element with the middle element. If the middle element is equal to the given element, then we return that position. Suppose the middle element is larger than the given element. In that case, it means that the given element will either lie in the left of the middle element or won't exist, so now the problem will reduce to searching the given element in the left half of the array. Similarly, if the middle element is smaller than the given element, the problem will be reduced to search the element in the right half of the array.

(See, Difference Between Binary Tree and BST)

Let's understand the binary search algorithm by taking an example:

The array we have taken above:

arr =  [1, 7, 6, 8, 9, 4]

After sorting it in increasing order,

arr = [1, 4, 6, 7, 8, 9]

Now, we have to search for '8' in this array. In this array, the middle element is '6', and '6' is smaller than '8', so we must search in the right half. So the array in which we have to search will be reduced to [7, 8, 9]

Now the middle element is '8', so we have found '8', so return the index of '8'.

If your thinking ability is paused in perplexity, then you must visit the Binary Search article on the Coding Ninjas platform.

Recommended: Binary Search problem for practice on Coding Ninjas Studio.

C++ Code for Binary Search

 

#include<bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int k, int n)
  {

   /*
       n = number of elements in the array
       k = The element which we have to search in the given array
   */
   int start = 0, end = n - 1; 

   /*
        Start and end will be the index of the first and last element of 
        that part of the array in which we are searching 
   */
   while(start <= end)
     {

             // mid is the index of the middle element
             int mid = (start + end) / 2;      
             if(arr[mid] == k) return mid;
             /*
                 middle element is less than k, so now we have to search in the
                 right half
             */

            else if(arr[mid] < k) start = mid + 1;  

            /*
                 middle element is greater than k, so now we have to search in
                 left half
             */
             else end = mid - 1;      
        }

    // if element not found return -1
    return -1;
  }

int main()
{
  int arr[6] = {1, 4, 6, 7, 8, 9};

  // Search k in the given array
  int k = 8;
  int foundAt = binarySearch(arr, k, 6);
  if(foundAt == -1) 
       cout<<"Element doesn't exist in the array!"<<endl;
  else 
       cout<<"Element found at the index "<<foundAt<<endl;
}

 

Output:
Element found at the index 4

Here, we can see that the array in which we have to search for the given element is getting halved at each iteration. So, the time complexity of the binary search algorithm is O(log(N)), where 'N' is the number of elements in the array.

See, Self Balancing Binary Trees

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Inbuilt Binary Search in C++

C++ has an inbuilt binary search function which we can use directly after importing the "algorithm" header.  It takes three input parameters -  start: Iterator pointing to the starting of the sorted sequence, end: Iterator pointing to the end of the sorted sequence, and target: The value we have to search in the sorted sequence and returns boolean value true or false. It returns true if the target element is present in the sequence; else returns false. This inbuilt binary search function uses a binary search algorithm and has O(log(N)) time complexity where 'N' is the number of elements in the sorted sequence.

Syntax:

binary_search(starting_iterator, ending_iterator, valueToSearch)

Returns: True/False

 

The following C++ code depicts the use of inbuilt binary search in C++:

 

#include <iostream>
#include<algorithm>
using namespace std;
int main()
{
     int arr[8]={2, 7, 9, 17, 25, 28, 78, 99};
     if(binary_search(begin(arr), end(arr), 25) == true)
       {
            cout<<"25 is present in the given array!"<<endl;
       }
     else 
       {
            cout<<"25 doesn't exist in the given array!"<<endl;
       }
     if(binary_search(begin(arr), end(arr), 26) == true)
       {
            cout<<"26 is present in the given array!"<<endl;
       }
     else 
       {
            cout<<"26 doesn't exist in the given array!"<<endl;
       }
}

 

Output:
25 is present in the given array!
26 doesn't exist in the given array!

 

Inbuilt Binary Search in Java

In the Java Arrays class, there is the "binarySearch()" method which uses a binary search algorithm to search a given element in a specified sorted array and returns the index of the element if found else returns a negative number.

 

Some Important Points:

  1.  If the given array is not sorted, then the results are undefined. 
  2. If the array contains multiple elements equal to the element we are searching for, then it is not guaranteed which one will be found by this method.
  3. If the element is present in the array, it returns its index. Otherwise, it returns  "(-(insertion point)-1)". The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element in the range greater than the key, or toIndex if all elements in the range are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

Syntax:

  1. public static int binarySearch(data_type[] a,data_type key)
    • Parameters: 
    • a: the array to be searched
    • key:  the value to be searched for
  2. public static int binarySearch(data_type[] a, int fromIndex, int toIndex, data_type key)
    • Parameters:
    • a: the array to be searched
    • fromIndex: the first index of the range to be searched (inclusive)
    • toIndex: the last index of the range to be searched (exclusive)
    • key: the value to be searched for

 

The following Java code depicts the use of inbuilt binary search in Java Arrays Class:

import java.util.Arrays;
class Main
{
    public static void main(String[] args)
    {
        int[] A = {2, 7, 9, 17, 25, 28, 78, 99};
        int key1 = 25;
        int key2 = 26;
 
        int index1 = Arrays.binarySearch(A, key1);
        int index2= Arrays.binarySearch(A, key2);
 
        if (index1 >= 0) {
            System.out.println("25 is found at index: " + index1);
        } else {
            System.out.println("25 doesn't exist in the given array!");
        }
        
        if (index2 >= 0) {
            System.out.println("26 is found at index " + index2);
        } else {
            System.out.println("26 doesn't exist in the given array!");
        }
    }
}

 

Output:
25 is found at index: 4
26 doesn't exist in the given array!

Check out this array problem - Merge 2 Sorted Arrays

Frequently Asked Questions

What is the time and space complexity of the Binary Search algorithm?

As we have seen in the algorithm, the problem is reduced to searching in half of the array of the previous iteration at each iteration. So, the algorithm's time complexity is O(logN), where “N” is the number of elements in the given array. Also, we are using constant space. Thus, the space complexity of the algorithm is O(1).

Is it necessary to have sorted data using a binary search algorithm?

Yes, it is necessary to have sorted data for applying a binary search algorithm as the whole algorithm is based on the fact that the given data is sorted.

 

Conclusion

This article discussed binary search, the time and space complexity of the binary search, and inbuilt binary search methods in C++ and Java. We have discussed in detail the input parameters and output of the inbuilt binary search in C++ and java.

Recommended Problems:

If you think that this blog helped you, then share it with your friends!. Refer to DSA C++  and DSA Java to learn more. Along with coding questions, you can also find the interview experience and interview bundle of scholars working in renowned product-based companies here. 

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Until then, All the best for your future endeavors, and Keep Coding.

Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass