Where should an element be located in the array so that the run time of the Binary search algorithm is O(log n)?
2 Answers
The first or last element will give the worst case complexity in binary search as you'll have to do maximum no of comparisons. Example:
1 2 3 4 5 6 7 8 9
Here searching for 1 will give you the worst case, with the result coming in 4th pass.
1 2 3 4 5 6 7 8
In this case, searching for 8 will give the worst case, with the result coming in 4 passes.
Note that in the second case searching for 1 (the first element) can be done in just 3 passes. (compare 1 & 4, compare 1 & 2 and finally 1)
So, if no. of elements are even, the last element gives the worst case.
This is assuming all arrays are 0 indexed. This happens due to considering the mid as float of (start + end) /2.
// Java implementation of iterative Binary Search
class BinarySearch
{ // Returns index of x if it is present in arr[], // else return -1 int binarySearch(int arr[], int x) { int l = 0, r = arr.length - 1; while (l <= r) { int m = l + (r-l)/2; // Check if x is present at mid if (arr[m] == x) return m; // If x greater, ignore left half if (arr[m] < x) l = m + 1; // If x is smaller, ignore right half else r = m - 1; } // if we reach here, then element was // not present return -1; } // Driver method to test above public static void main(String args[]) { BinarySearch ob = new BinarySearch(); int arr[] = {2, 3, 4, 10, 40}; int n = arr.length; int x = 10; int result = ob.binarySearch(arr, x); if (result == -1) System.out.println("Element not present"); else System.out.println("Element found at " + "index " + result); }
}Time Complexity: The time complexity of Binary Search can be written as
T(n) = T(n/2) + c The above recurrence can be solved either using Recurrence T ree method or Master method. It falls in case II of Master Method and solution of the recurrence is Theta(Logn).
Auxiliary Space: O(1) in case of iterative implementation. In case of recursive implementation, O(Logn) recursion call stack space.
