Time Complexity of Binary Search
Determine the time complexity (Big-O notation) of the following algorithm.
public int binarySearch(int[] sorted, int target) {
int low = 0, high = sorted.length - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(sorted[mid] == target) return mid;
else if(sorted[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
A
O(n)
B
O(1)
C
O(n log n)
D
O(log n)
APFIVE