Binary Search is a highly efficient algorithm used to find an element in a sorted array. The main idea behind Binary Search is to repeatedly divide the search interval in half and compare the middle element of the interval with the target value. If the target value matches the middle element, the search is successful. If the target value is less than the middle element, the search continues in the lower half of the array; otherwise, it continues in the upper half.

## How Binary Search Works

- Start with the entire array as the search interval.
- Find the middle element of the array.
- Compare the middle element with the target value.
- If the middle element is equal to the target value, return the index of the middle element.
- If the target value is less than the middle element, narrow the interval to the lower half of the array.
- If the target value is greater than the middle element, narrow the interval to the upper half of the array.
- Repeat the process until the interval is empty.

## Python Implementation of Binary Search

```
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
# If x is greater, ignore left half
if arr[mid] < x:
low = mid + 1
# If x is smaller, ignore right half
elif arr[mid] > x:
high = mid - 1
# x is present at mid
else:
return mid
# x is not present in array
return -1
# Example usage:
arr = [2, 3, 4, 10, 40]
x = 10
# Function call
result = binary_search(arr, x)
if result != -1:
print("Element is present at index", str(result))
else:
print("Element is not present in array")
```

## Explanation of the Code

- The function
`binary_search(arr, x)`

takes a sorted array`arr`

and a target value`x`

as input. - It initializes the
`low`

and`high`

pointers to the start and end of the array, respectively. - The middle element is calculated using the formula
`(high + low) // 2`

. - If the middle element is equal to the target value
`x`

, the function returns the index of the middle element. - If the middle element is greater than
`x`

, the search continues in the lower half; otherwise, it continues in the upper half. - If the element is not found, the function returns
`-1`

.

## Complexity Analysis

Binary Search has a time complexity of O(log n) because the search interval is halved with each iteration. This makes it much faster than linear search algorithms for large datasets.

Space complexity is O(1) because it only requires a constant amount of additional space.