# Binary Search

Binary Search is a fundamental search algorithm used to find the position of a target element within a sorted array. It employs a divide-and-conquer strategy to efficiently narrow down the search space, making it significantly faster than linear search for larger datasets.

## Problem Statement and Description

Given a sorted array and a target element, the problem is to determine whether the element exists in the array and, if so, return its index. Binary Search compares the target element with the middle element of the array, and based on the comparison result, halves the search space by discarding the half where the element cannot exist.

## Example

Consider the sorted array: [-4, 2, 3, 7, 9, 12, 17, 19, 21]. Let's find the positions of a few elements using Binary Search:

• Target: 9 → Found at index 4
• Target: 2 → Found at index 1
• Target: 21 → Found at index 8
• Target: 3 → Found at index 2

## Idea to Solve the Problem

Binary Search operates on the principle of narrowing down the search interval by half at each step. The steps are as follows:

1. Find the middle element of the current search interval.
2. Compare the middle element with the target element.
3. If the middle element is equal to the target, return its index.
4. If the middle element is greater than the target, narrow the interval to the lower half.
5. If the middle element is less than the target, narrow the interval to the upper half.
6. Repeat steps 1 to 5 until the interval becomes empty or the target is found.

## Pseudocode

``````function find_node(arr, size, element)
i = 0, j = size - 1
while j >= i
mid = (i + j) / 2
if arr[mid] > element
j = mid - 1
else if arr[mid] < element
i = mid + 1
else
return mid
return -1``````

## Algorithm Explanation

The `find_node` function implements the Binary Search algorithm. It maintains two pointers, `i` and `j`, representing the start and end of the current search interval. The `mid` is calculated as the average of `i` and `j`. If the element at `mid` is greater than the target, the search interval is narrowed to the lower half; if it's less, the interval is narrowed to the upper half. If the element is found, its index is returned. If the interval becomes empty, the element is not in the array.

## Time Complexity

Binary Search has a time complexity of O(log n), where n is the number of elements in the array. This efficiency comes from halving the search interval in each step, allowing it to quickly converge to the target.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.