# Count of elements that are binary searchable in the given array

Given an array **arr[]** consisting of **N **integers, the task is to find the maximum count of integers that are binary searchable in the given array.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr[] = {1, 3, 2}Output:2Explanation:arr[0], arr[1] can be found.

Input:arr[] = {3, 2, 1, 10, 23, 22, 21}Output:3Explanation:arr[1], arr[3], arr[5] can be found using binary search irrespective of whether the array is sorted or not.

**Approach:** The given problem can be solved by searching for each element separately in the array using the Binary Search approach and increment the count of those integers that exist in the array. Follow the below steps to solve the problem:

- Make a variable
**count = 0**, that will store the count of elements that are binary searchable. - For each element perform the binary search in the range
**[0, N)**as:- Initialize the variable
**l**as**0**and**r**as**N-1**and perform the binary search for**arr[i]**. - For each iteration of the while loop till
**l**is less than equal to**r,**calculate the mid-value denoted by**(l + r)/2**.- If
**arr[mid]**equals**arr[i]**then increment**count**by**1**. - If
**arr[mid]**is less than**arr[i],**then change**l**as**mid + 1**. - Otherwise, change
**r**as**mid – 1**.

- If

- Initialize the variable
- The final answer will be stored in the variable
**count**.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the total count of` `// elements that are binary searchable` `int` `totalBinarySearchable(vector<` `int` `> arr)` `{` ` ` `// Stores the count of element that` ` ` `// are binary searchable` ` ` `int` `count = 0;` ` ` `int` `N = arr.size();` ` ` `// For each element check if it can` ` ` `// be found by doing a binary search` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// Binary search range` ` ` `int` `l = 0, r = N - 1;` ` ` `// Do a binary Search` ` ` `while` `(l <= r) {` ` ` `int` `mid = (l + r) / 2;` ` ` `// Array element found` ` ` `if` `(arr[mid] == arr[i]) {` ` ` `count++;` ` ` `break` `;` ` ` `}` ` ` `if` `(arr[mid] < arr[i]) {` ` ` `l = mid + 1;` ` ` `}` ` ` `else` `{` ` ` `r = mid - 1;` ` ` `}` ` ` `}` ` ` `}` ` ` `// Return the total count` ` ` `return` `count;` `}` `// Driver Code` `int` `main()` `{` ` ` `vector<` `int` `> arr = { 3, 2, 1, 10,` ` ` `23, 22, 21 };` ` ` `cout << totalBinarySearchable(arr);` ` ` `return` `0;` `}` |

## Java

`// Java code for the above approach` `import` `java.io.*;` `class` `GFG` `{` ` ` ` ` `// Function to find the total count of` ` ` `// elements that are binary searchable` ` ` `static` `int` `totalBinarySearchable(` `int` `[] arr)` ` ` `{` ` ` `// Stores the count of element that` ` ` `// are binary searchable` ` ` `int` `count = ` `0` `;` ` ` `int` `N = arr.length;` ` ` `// For each element check if it can` ` ` `// be found by doing a binary search` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++) {` ` ` `// Binary search range` ` ` `int` `l = ` `0` `, r = N - ` `1` `;` ` ` `// Do a binary Search` ` ` `while` `(l <= r) {` ` ` `int` `mid = (l + r) / ` `2` `;` ` ` `// Array element found` ` ` `if` `(arr[mid] == arr[i]) {` ` ` `count++;` ` ` `break` `;` ` ` `}` ` ` `if` `(arr[mid] < arr[i]) {` ` ` `l = mid + ` `1` `;` ` ` `}` ` ` `else` `{` ` ` `r = mid - ` `1` `;` ` ` `}` ` ` `}` ` ` `}` ` ` `// Return the total count` ` ` `return` `count;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `[] arr = { ` `3` `, ` `2` `, ` `1` `, ` `10` `, ` `23` `, ` `22` `, ` `21` `};` ` ` `System.out.println(totalBinarySearchable(arr));` ` ` `}` `}` `// This code is contributed by Potta Lokesh` |

## Python3

`# python program for the above approach` `# Function to find the total count of` `# elements that are binary searchable` `def` `totalBinarySearchable(arr):` ` ` `# Stores the count of element that` ` ` `# are binary searchable` ` ` `count ` `=` `0` ` ` `N ` `=` `len` `(arr)` ` ` `# For each element check if it can` ` ` `# be found by doing a binary search` ` ` `for` `i ` `in` `range` `(` `0` `, N):` ` ` `# Binary search range` ` ` `l ` `=` `0` ` ` `r ` `=` `N ` `-` `1` ` ` `# Do a binary Search` ` ` `while` `(l <` `=` `r):` ` ` `mid ` `=` `(l ` `+` `r) ` `/` `/` `2` ` ` `# Array element found` ` ` `if` `(arr[mid] ` `=` `=` `arr[i]):` ` ` `count ` `+` `=` `1` ` ` `break` ` ` `if` `(arr[mid] < arr[i]):` ` ` `l ` `=` `mid ` `+` `1` ` ` `else` `:` ` ` `r ` `=` `mid ` `-` `1` ` ` `# Return the total count` ` ` `return` `count` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `arr ` `=` `[` `3` `, ` `2` `, ` `1` `, ` `10` `,` ` ` `23` `, ` `22` `, ` `21` `]` ` ` `print` `(totalBinarySearchable(arr))` ` ` `# This code is contributed by rakeshsahni` |

## C#

`// C# code for the above approach` `using` `System;` `public` `class` `GFG` `{` ` ` ` ` `// Function to find the total count of` ` ` `// elements that are binary searchable` ` ` `static` `int` `totalBinarySearchable(` `int` `[] arr)` ` ` `{` ` ` `// Stores the count of element that` ` ` `// are binary searchable` ` ` `int` `count = 0;` ` ` `int` `N = arr.Length;` ` ` `// For each element check if it can` ` ` `// be found by doing a binary search` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// Binary search range` ` ` `int` `l = 0, r = N - 1;` ` ` `// Do a binary Search` ` ` `while` `(l <= r) {` ` ` `int` `mid = (l + r) / 2;` ` ` `// Array element found` ` ` `if` `(arr[mid] == arr[i]) {` ` ` `count++;` ` ` `break` `;` ` ` `}` ` ` `if` `(arr[mid] < arr[i]) {` ` ` `l = mid + 1;` ` ` `}` ` ` `else` `{` ` ` `r = mid - 1;` ` ` `}` ` ` `}` ` ` `}` ` ` `// Return the total count` ` ` `return` `count;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main(` `string` `[] args)` ` ` `{` ` ` `int` `[] arr = { 3, 2, 1, 10, 23, 22, 21 };` ` ` `Console.WriteLine(totalBinarySearchable(arr));` ` ` `}` `}` `// This code is contributed by rrrtnx.` |

## Javascript

`<script>` `// Javascript program for the above approach` `// Function to find the total count of` `// elements that are binary searchable` `function` `totalBinarySearchable(arr)` `{` ` ` `// Stores the count of element that` ` ` `// are binary searchable` ` ` `let count = 0;` ` ` `let N = arr.length;` ` ` `// For each element check if it can` ` ` `// be found by doing a binary search` ` ` `for` `(let i = 0; i < N; i++)` ` ` `{` ` ` ` ` `// Binary search range` ` ` `let l = 0,` ` ` `r = N - 1;` ` ` `// Do a binary Search` ` ` `while` `(l <= r) {` ` ` `let mid = Math.floor((l + r) / 2);` ` ` `// Array element found` ` ` `if` `(arr[mid] == arr[i]) {` ` ` `count++;` ` ` `break` `;` ` ` `}` ` ` `if` `(arr[mid] < arr[i]) {` ` ` `l = mid + 1;` ` ` `} ` `else` `{` ` ` `r = mid - 1;` ` ` `}` ` ` `}` ` ` `}` ` ` `// Return the total count` ` ` `return` `count;` `}` `// Driver Code` `let arr = [3, 2, 1, 10, 23, 22, 21];` `document.write(totalBinarySearchable(arr));` `// This code is contributed by gfgking.` `</script>` |

**Output:**

3

**Time Complexity:** O(N*log(N))**Auxiliary Space:** O(1)