I am studying about binary search tree and I have written a method to perform binary search in list of array java. However, I am trying to work out the time complexity of this algorithm. but i am new this topic and I am not sure how to work out the time complexity using BIG O notation.
public <T extends Comparable<T int binarySearch(T[] array,T target) {
int first = 0, last = array.length-1; // initially search in the whole array
while (first <= last) {// still at least one element in search space
// calculate median index, halfway between first and last indices. . .
int median = (first+last)/2;
// . . . and get the value there
int comparison = array[median].compareTo[target];
if (comparison == 0) {// target value found
return median;
} else if (comparison > 0) {// median value is larger than target
last = median-1; // search further in lower half of search space
} else {// median value is smaller than target
first = median+1; // search further in upper half of search space
}
}
return -1; // ran out of search
The complexity is O(logn).
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments