Binary Search
Code
Python
- Solution 1
- Solution 2
def binarySearch(array, target):
return binarySearchHelper(array, target, 0, len(array) - 1)
def binarySearchHelper(array, target, left, right):
if left > right:
return -1
middle = (left + right) // 2
potentialMatch = array[middle]
if target == potentialMatch:
return middle
elif target < potentialMatch:
return binarySearchHelper(array, target, left, middle - 1)
else:
return binarySearchHelper(array, target, middle + 1, right)
JavaScript
- Solution 1
- Solution 2
function binarySearch(array, target) {
return binarySearchHelper(array, target, 0, array.length - 1);
}
function binarySearchHelper(array, target, left, right) {
if (left > right) return -1;
const middle = Math.floor((left + right) / 2);
const potentialMatch = array[middle];
if (target === potentialMatch) {
return middle;
} else if (target < potentialMatch) {
return binarySearchHelper(array, target, left, middle - 1);
} else {
return binarySearchHelper(array, target, middle + 1, right);
}
}
exports.binarySearch = binarySearch;
TypeScript
- Solution 1
- Solution 2
export function binarySearch(array: number[], target: number) {
return binarySearchHelper(array, target, 0, array.length - 1);
}
function binarySearchHelper(array: number[], target: number, left: number, right: number): number {
if (left > right) return -1;
const middle = Math.floor((left + right) / 2);
const potentialMatch = array[middle];
if (target === potentialMatch) {
return middle;
} else if (target < potentialMatch) {
return binarySearchHelper(array, target, left, middle - 1);
} else {
return binarySearchHelper(array, target, middle + 1, right);
}
}
Java
- Solution 1
- Solution 2
class Program {
public static int binarySearch(int[] array, int target) {
return binarySearch(array, target, 0, array.length - 1);
}
public static int binarySearch(int[] array, int target, int left, int right) {
if (left > right) {
return -1;
}
int middle = (left + right) / 2;
int potentialMatch = array[middle];
if (target == potentialMatch) {
return middle;
} else if (target < potentialMatch) {
return binarySearch(array, target, left, middle - 1);
} else {
return binarySearch(array, target, middle + 1, right);
}
}
}
C++
- Solution 1
- Solution 2
#include <vector>
using namespace std;
int binarySearch(vector<int> array, int target);
int binarySearchHelper(vector<int> array, int target, int left, int right);
int binarySearch(vector<int> array, int target) {
return binarySearchHelper(array, target, 0, array.size() - 1);
}
int binarySearchHelper(vector<int> array, int target, int left, int right) {
if (left > right) {
return -1;
}
int middle = (left + right) / 2;
int potentialMatch = array[middle];
if (target == potentialMatch) {
return middle;
} else if (target < potentialMatch) {
return binarySearchHelper(array, target, left, middle - 1);
} else {
return binarySearchHelper(array, target, middle + 1, right);
}
}
Space-Time Complexity
- Solution 1
- Solution 2
| Time | Space | |
|---|---|---|
| Worse | O(log(n)) | O(log(n)) |
Where n is the length of the input array