CODEWITHSUNDEEP
searchruntimetime-complexitybinary-search
mstjepan
mstjepan

Reputation: 51

What is the worst case for binary search

Where should an element be located in the array so that the run time of the Binary search algorithm is O(log n)?

Upvotes: 4

Views: 27524

Answers (2)

Yuvraj Jaiswal
Yuvraj Jaiswal

Reputation: 1723

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.

Upvotes: 2

Gautam Kumar
Gautam Kumar

Reputation: 31

// 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.

Upvotes: 1

Related Questions