## Table of Contents

Binary search is an efficient algorithm for finding the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half until the value is found or it is clear that the value is not present in the array.

#### ALGORITHM :

Here is an overview of the binary search algorithm:

- Set the lower and upper bounds of the search interval to the first and last elements of the array, respectively.
- If the search interval is empty (the lower bound is greater than the upper bound), the target value is not present in the array and the search is terminated.
- Calculate the midpoint of the search interval.
- If the target value is equal to the value at the midpoint, the search is successful and the position of the target value is returned.
- If the target value is less than the value at the midpoint, set the upper bound of the search interval to the midpoint – 1 and go back to step 2.
- If the target value is greater than the value at the midpoint, set the lower bound of the search interval to the midpoint + 1 and go back to step 2.

There are two main approaches to implementing binary search:

- Iterative Method:
- Recursive Method:

#### Iterative Method:

The iterative method involves using a loop to perform the search.

##### Here is an example of the binary search algorithm implemented using a recursive method in C++:

```
int binarySearch(int arr[], int target, int low, int high) {
while (low <= high) {
int mid = (low + high) / 2; // Calculate midpoint
if (arr[mid] == target) {
return mid; // Target found at midpoint
} else if (arr[mid] < target) {
low = mid + 1; // Search right half
} else {
high = mid - 1; // Search left half
}
}
return -1; // Target not found
}
```

#### Recursive Method:

The recursive method involves using a function to perform the search.

##### Here is an example of the binary search algorithm implemented using a recursive method in C++:

```
int binarySearch(int arr[], int target, int low, int high) {
if (low > high) {
return -1; // Target not found
}
int mid = (low + high) / 2; // Calculate midpoint
if (arr[mid] == target) {
return mid; // Target found at midpoint
} else if (arr[mid] < target) {
return binarySearch(arr, target, mid + 1, high); // Search right half
} else {
return binarySearch(arr, target, low, mid - 1); // Search left half
}
}
```

##### Here is the same algorithm implemented in Python:

```
def binary_search(arr, target, low, high):
if low > high:
return -1 # Target not found
mid = (low + high) // 2 # Calculate midpoint
if arr[mid] == target:
return mid # Target found at midpoint
elif arr[mid] < target:
return binary_search(arr, target, mid + 1, high) # Search right half
else:
return binary
```

##### Here is the binary search algorithm implemented using an iterative method in Java:

```
public int binarySearch(int[] arr, int target, int low, int high) {
while (low <= high) {
int mid = (low + high) / 2; // Calculate midpoint
if (arr[mid] == target) {
return mid; // Target found at midpoint
} else if (arr[mid] < target) {
low = mid + 1; // Search right half
} else {
high = mid - 1; // Search left half
}
}
return -1; // Target not found
}
```