-4

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
khelwood
  • 55,782
  • 14
  • 81
  • 108
Jhon Smith
  • 11
  • 4

1 Answers1

0

The complexity is O(logn).

Wikipedia

Nikolay Bonev
  • 151
  • 6
  • Can you please explain why is it O(logN) and not O(n) – Jhon Smith May 08 '17 at 16:01
  • If the complexity is O(N) that meanes we are checking every element in the structure to find the wanted one. In Binary search the elements are ordered in increasing or decreasing order. Because of this we can check the middle element of the structure and determine is the current element the wanted or in which half it is. For example if we have an array with elements: [1,2,3,4,5,6,7] and we are searching x = 5 we start with the middle element that is x > 4 and we choose the right half. Again check the middle element that is 6. x < 6 and choose left half. x == 5. – Nikolay Bonev May 08 '17 at 17:09