.png)
Binary Search on Arrays
Binary Search is a highly efficient searching algorithm used to find the position of a target element in a sorted array or monotonic search space. Instead of scanning elements one by one, Binary Search repeatedly divides the search space into halves, reducing the time complexity to O(log N).
What is Binary Search?
Binary Search works by comparing the target value with the middle element of the array:
- If the middle element equals the target → search ends.
- If the target is smaller → search continues in the left half.
- If the target is larger → search continues in the right half.
This divide-and-conquer strategy makes Binary Search much faster than linear search for large datasets.
Conditions to Apply Binary Search
To successfully apply Binary Search:
- The data structure must be sorted (ascending or descending).
- Random access to elements should be possible (array or array-like structure).
- The comparison operation must take constant time.
Binary Search Algorithm (Step-by-Step)
- Initialize two pointers:
- low = 0
- high = n - 1
Find the middle index:
mid = low + (high - low) / 2- Compare arr[mid] with the target value.
- Based on comparison:
- If equal → return index
- If smaller → search right half
- If larger → search left half
- Repeat until the element is found or the search space is exhausted.
Example
Array:
arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
Target: 23
Binary Search will:
- Start from middle → 16
- Move right
- Reach 23 → element found
Ways to Implement Binary Search
Binary Search can be implemented in two ways:
- Iterative Binary Search
- Recursive Binary Search
Iterative Binary Search Algorithm
Time Complexity: O(log N)
Space Complexity: O(1)
This approach uses a loop and does not consume extra stack memory.
C++ Implementation
#include
#include
using namespace std;
int binarySearch(vector& arr, int x) {
int low = 0, high = arr.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
else if (arr[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main() {
vector arr = {2, 3, 4, 10, 40};
int x = 10;
int result = binarySearch(arr, x);
if (result == -1)
cout << "Element not found";
else
cout << "Element found at index " << result;
return 0;
}
C Implementation
#include
int binarySearch(int arr[], int n, int x) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
else if (arr[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, n, x);
if(result == -1)
printf("Element not found");
else
printf("Element found at index %d", result);
return 0;
}
Java Implementation
class BinarySearch {
static int binarySearch(int[] arr, int x) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
else if (arr[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {2, 3, 4, 10, 40};
int x = 10;
int result = binarySearch(arr, x);
if(result == -1)
System.out.println("Element not found");
else
System.out.println("Element found at index " + result);
}
}
Python Implementation
def binary_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = low + (high - low) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, x)
if result == -1:
print("Element not found")
else:
print("Element found at index", result)
C# Implementation
using System;
class BinarySearch {
static int Search(int[] arr, int x) {
int low = 0, high = arr.Length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
else if (arr[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
static void Main() {
int[] arr = {2, 3, 4, 10, 40};
int x = 10;
int result = Search(arr, x);
if(result == -1)
Console.WriteLine("Element not found");
else
Console.WriteLine("Element found at index " + result);
}
}
JavaScript Implementation
function binarySearch(arr, x) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
let mid = Math.floor(low + (high - low) / 2);
if (arr[mid] === x)
return mid;
else if (arr[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
let arr = [2, 3, 4, 10, 40];
let x = 10;
let result = binarySearch(arr, x);
if(result === -1)
console.log("Element not found");
else
console.log("Element found at index " + result);
PHP Implementation
Output
Element found at index 3
Recursive Binary Search Algorithm
Recursive Binary Search uses the divide-and-conquer technique.
Instead of using a loop, the algorithm calls itself recursively, reducing the search space by half in each call until the target element is found or the range becomes invalid.
How Recursive Binary Search Works
- Find the middle index of the current search range.
- Compare the middle element with the target value.
- If they are equal, return the index.
- If the target is smaller, recursively search the left subarray.
- If the target is larger, recursively search the right subarray.
- If the range becomes invalid (low > high), return -1.
C Implementation
#include
int binarySearch(int arr[], int low, int high, int x) {
if (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);
return binarySearch(arr, mid + 1, high, x);
}
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if(result == -1)
printf("Element not found");
else
printf("Element found at index %d", result);
return 0;
}
Java Implementation
class RecursiveBinarySearch {
static int binarySearch(int[] arr, int low, int high, int x) {
if (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);
return binarySearch(arr, mid + 1, high, x);
}
return -1;
}
public static void main(String[] args) {
int[] arr = {2, 3, 4, 10, 40};
int x = 10;
int result = binarySearch(arr, 0, arr.length - 1, x);
if(result == -1)
System.out.println("Element not found");
else
System.out.println("Element found at index " + result);
}
}
Python Implementation
def binary_search(arr, low, high, x):
if low <= high:
mid = low + (high - low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
return -1
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, 0, len(arr) - 1, x)
if result == -1:
print("Element not found")
else:
print("Element found at index", result)
C# Implementation
using System;
class RecursiveBinarySearch {
static int BinarySearch(int[] arr, int low, int high, int x) {
if (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return BinarySearch(arr, low, mid - 1, x);
return BinarySearch(arr, mid + 1, high, x);
}
return -1;
}
static void Main() {
int[] arr = {2, 3, 4, 10, 40};
int x = 10;
int result = BinarySearch(arr, 0, arr.Length - 1, x);
if(result == -1)
Console.WriteLine("Element not found");
else
Console.WriteLine("Element found at index " + result);
}
}
JavaScript Implementation
function binarySearch(arr, low, high, x) {
if (low <= high) {
let mid = Math.floor(low + (high - low) / 2);
if (arr[mid] === x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);
return binarySearch(arr, mid + 1, high, x);
}
return -1;
}
let arr = [2, 3, 4, 10, 40];
let x = 10;
let result = binarySearch(arr, 0, arr.length - 1, x);
if(result === -1)
console.log("Element not found");
else
console.log("Element found at index " + result);
PHP Implementation
$x)
return binarySearch($arr, $low, $mid - 1, $x);
return binarySearch($arr, $mid + 1, $high, $x);
}
return -1;
}
$arr = [2, 3, 4, 10, 40];
$x = 10;
$result = binarySearch($arr, 0, count($arr) - 1, $x);
if($result == -1)
echo "Element not found";
else
echo "Element found at index ".$result;
?>
Output
Element found at index 3
Complexity Analysis
| Case | Time Complexity |
|---|---|
| Best Case | O(1) |
| Average Case | O(log N) |
| Worst Case | O(log N) |
Auxiliary Space:
- Iterative: O(1)
- Recursive: O(log N)
Applications of Binary Search
- Searching in sorted arrays
- Finding first/last occurrence
- Rotated sorted arrays
- Database indexing (B-Trees)
- Version control debugging (git bisect)
- Machine learning hyperparameter tuning
- Competitive programming optimization problems
Problems Based on Binary Search
- Square Root of an Integer
- First and Last Position in Sorted Array
- Count 1’s in a Sorted Binary Array
- Search in Rotated Sorted Array
- Minimum Element in Rotated Array
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
