UNIT II - Divide and Conquer: Binary Search

 Binary Search

Introduction:

         Binary Search is a powerful search algorithm based on the Divide and Conquer approach. It efficiently finds a specific target element in a sorted array by repeatedly dividing the search space in half. This article explores the Binary Search algorithm, along with its examples, characteristics, advantages, disadvantages, and necessary diagrams.

Binary Search Algorithm:

Start with the middle element of the sorted array.
If the middle element is the target element, return its index.
If the target element is less than the middle element, search in the left half of the array.
If the target element is greater than the middle element, search in the right half of the array.
Repeat steps 1-4 on the selected half until the target element is found or the search space becomes empty.

Example: Consider a sorted array: [1, 3, 5, 7, 9, 11, 13, 15] Target element: 7Start with the middle element: 9 (index 4).
As 7 < 9, we search in the left subarray [1, 3, 5].
The middle element of the left subarray is 3 (index 1).
As 7 > 3, we search in the right subarray [7, 9].
The middle element of the right subarray is 7 (index 3), which is the target element.

Characteristics:

Binary Search is applicable only to sorted arrays.
It is a Divide and Conquer algorithm, reducing the search space by half at each step.
The time complexity of Binary Search is O(log n), making it efficient for large datasets.

Advantages:

Efficiency: Binary Search has a logarithmic time complexity, making it highly efficient for large datasets.
Simplicity: The algorithm is straightforward to understand and implement.
Versatility: Binary Search can be adapted to work on various data structures with sorted elements, such as linked lists.

Disadvantages:

Requirement of Sorted Data: The array must be sorted before applying Binary Search, which can add an extra preprocessing step.
Limited Applicability: Binary Search is not suitable for unsorted or dynamically changing data.

Diagram: Below is an illustration of the Binary Search process for the example given earlier, where the target element is 7:

Sorted Array: [1, 3, 5, 7, 9, 11, 13, 15] Target Element: 7

Step 1: Low Index: 0, High Index: 7 Middle Element: 9 (Index: 4)

Step 2: Low Index: 0, High Index: 3 Middle Element: 3 (Index: 1)

Step 3: Low Index: 2, High Index: 3 Middle Element: 7 (Index: 3) Target Element Found!