Binary Serch

Understanding Time Complexity ( O(\log n) ) with Binary Search

Binary Search is an efficient algorithm used to find an element in a sorted array. The key idea is to repeatedly divide the search space in half, which gives it a logarithmic time complexity ( O(\log n) ).

How Binary Search Works

1. Start with the entire array:

   • Consider the middle element.

   • If the middle element is the target value, the search is complete.

   • If the target value is less than the middle element, repeat the search on the left half of the array.

   • If the target value is greater than the middle element, repeat the search on the right half of the array.

2. Repeat the process until the target is found or the search space is reduced to zero.

Binary Search Code Example in Java

Here's a simple implementation of Binary Search in Java:

public class BinarySearch {
    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 7;
        int result = binarySearch(sortedArray, target);

        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }

    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;  // Calculate the mid index

            // Check if target is present at mid
            if (array[mid] == target) {
                return mid;
            }

            // If target greater, ignore left half
            if (array[mid] < target) {
                left = mid + 1;
            }
            // If target is smaller, ignore right half
            else {
                right = mid - 1;
            }
        }

        // Target not found
        return -1;
    }
}

Breaking Down the Time Complexity

Let's analyze why the time complexity of Binary Search is ( O(\log n) ):

1. Initial Search Space:

   • The algorithm starts with an array of size ( n ).

2. Halving the Search Space:

   • Each time we perform a comparison (checking the middle element), we eliminate half of the remaining elements from consideration.

   • In the first step, the search space is reduced from ( n ) elements to ( n/2 ) elements.

   • In the second step, it's reduced to ( n/4 ) elements, then to ( n/8 ), and so on.

3. Number of Iterations:

   • The number of times we can halve ( n ) until we are left with 1 element is ( \log_2(n) ).

   • This is because halving the array ( k ) times gives us ( n/2^k ). When ( n/2^k = 1 ), ( k ) is approximately ( \log_2(n) ).

4. Conclusion:

   • The algorithm runs in ( O(\log n) ) time because the number of iterations required to reduce the search space to one element is proportional to ( \log n ).

Example Walkthrough

Let's say we have an array of 16 elements and we are looking for the target value:

1. First iteration:

   • Search space: 16 elements.

   • Midpoint is checked, and the search space is reduced to 8 elements.

2. Second iteration:

   • Search space: 8 elements.

   • Midpoint is checked, and the search space is reduced to 4 elements.

3. Third iteration:

   • Search space: 4 elements.

   • Midpoint is checked, and the search space is reduced to 2 elements.

4. Fourth iteration:

   • Search space: 2 elements.

   • Midpoint is checked, and the search space is reduced to 1 element.

After four iterations, the search is complete. The number of iterations ( k ) is such that ( 2^k = n ), leading to ( k = \log_2(n) ).

Why ( O(\log n) )?

• The time complexity ( O(\log n) ) arises because each comparison in binary search reduces the problem size by half.

• This logarithmic reduction in problem size means that the number of steps grows logarithmically with the input size.

Summary

Binary search is efficient with a time complexity of ( O(\log n) ) because it systematically reduces the search space by half with each iteration. The logarithmic nature of this reduction means that even very large arrays can be searched quickly. For example, an array with 1,000,000 elements can be searched in about 20 comparisons using binary search, making it much faster than a linear search that would require up to 1,000,000 comparisons in the worst case.