Binary Search Algorithm Code Implementations
Complete Binary Search Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Binary Search Algorithm Guide ยท Launch Interactive Visualizer
C++ Implementation
// Binary Search Implementation in C++
#include <iostream>
#include <vector>
#include <algorithm>
class BinarySearch {
public:
static int binarySearch(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // Element found
} else if (arr[mid] < target) {
left = mid + 1; // Search right half
} else {
right = mid - 1; // Search left half
}
}
return -1; // Element not found
}
// Binary Search with first occurrence
static int binarySearchFirst(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid;
right = mid - 1; // Continue searching left for first occurrence
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
// Binary Search with last occurrence
static int binarySearchLast(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid;
left = mid + 1; // Continue searching right for last occurrence
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
// Binary Search for insertion point
static int binarySearchInsertion(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
// Recursive Binary Search
static int binarySearchRecursive(const std::vector<int>& arr, int target) {
return binarySearchRecursiveHelper(arr, target, 0, arr.size() - 1);
}
private:
static int binarySearchRecursiveHelper(const std::vector<int>& arr, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursiveHelper(arr, target, mid + 1, right);
} else {
return binarySearchRecursiveHelper(arr, target, left, mid - 1);
}
}
public:
// Binary Search using std::binary_search
static int binarySearchSTL(const std::vector<int>& arr, int target) {
auto it = std::lower_bound(arr.begin(), arr.end(), target);
if (it != arr.end() && *it == target) {
return std::distance(arr.begin(), it);
}
return -1;
}
};JAVA Implementation
// Binary Search Implementation in Java
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // Element found
} else if (arr[mid] < target) {
left = mid + 1; // Search right half
} else {
right = mid - 1; // Search left half
}
}
return -1; // Element not found
}
// Binary Search with first occurrence
public static int binarySearchFirst(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid;
right = mid - 1; // Continue searching left for first occurrence
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
// Binary Search with last occurrence
public static int binarySearchLast(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid;
left = mid + 1; // Continue searching right for last occurrence
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
// Binary Search for insertion point
public static int binarySearchInsertion(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
// Recursive Binary Search
public static int binarySearchRecursive(int[] arr, int target) {
return binarySearchRecursiveHelper(arr, target, 0, arr.length - 1);
}
private static int binarySearchRecursiveHelper(int[] arr, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursiveHelper(arr, target, mid + 1, right);
} else {
return binarySearchRecursiveHelper(arr, target, left, mid - 1);
}
}
}JAVASCRIPT Implementation
// Binary Search Implementation in JavaScript
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid; // Element found
} else if (arr[mid] < target) {
left = mid + 1; // Search right half
} else {
right = mid - 1; // Search left half
}
}
return -1; // Element not found
}
// Binary Search with first occurrence
function binarySearchFirst(arr, target) {
let left = 0;
let right = arr.length - 1;
let result = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
result = mid;
right = mid - 1; // Continue searching left for first occurrence
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
// Binary Search with last occurrence
function binarySearchLast(arr, target) {
let left = 0;
let right = arr.length - 1;
let result = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
result = mid;
left = mid + 1; // Continue searching right for last occurrence
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
// Binary Search for insertion point
function binarySearchInsertion(arr, target) {
let left = 0;
let right = arr.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
// Recursive Binary Search
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
if (left > right) {
return -1;
}
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursive(arr, target, mid + 1, right);
} else {
return binarySearchRecursive(arr, target, left, mid - 1);
}
}PYTHON Implementation
# Binary Search Implementation in Python
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid # Element found
elif arr[mid] < target:
left = mid + 1 # Search right half
else:
right = mid - 1 # Search left half
return -1 # Element not found
# Binary Search with first occurrence
def binary_search_first(arr, target):
left = 0
right = len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
right = mid - 1 # Continue searching left for first occurrence
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
# Binary Search with last occurrence
def binary_search_last(arr, target):
left = 0
right = len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
left = mid + 1 # Continue searching right for last occurrence
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
# Binary Search for insertion point
def binary_search_insertion(arr, target):
left = 0
right = len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
# Recursive Binary Search
def binary_search_recursive(arr, target, left=0, right=None):
if right is None:
right = len(arr) - 1
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)