Binary search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half. Here’s a step-by-step explanation, an example, and code in various programming languages to help you understand and implement binary search.

### Understanding Binary Search

**Objective**: Given a sorted array, find the position of a target value using binary search.

### Steps to Implement Binary Search

**Initialize Pointers**: Set up two pointers:`low`

(starting at the beginning of the array) and`high`

(starting at the end of the array).**Calculate the Middle Index**: Find the middle index of the current search range using`(low + high) // 2`

.**Compare the Target Value**:

- If the target value is equal to the middle element, return the middle index.
- If the target value is less than the middle element, narrow the search range to the left half (i.e., adjust
`high`

to`mid - 1`

). - If the target value is greater than the middle element, narrow the search range to the right half (i.e., adjust
`low`

to`mid + 1`

).

**Repeat**the process until`low`

exceeds`high`

. If the target value is not found, return an indication that the value is not present (e.g.,`-1`

).

### Example

Consider a sorted array: `[1, 3, 5, 7, 9, 11]`

**Target Value**: `7`

- Initialize
`low = 0`

and`high = 5`

(last index). - Compute
`mid = (0 + 5) // 2 = 2`

. The middle element is`5`

. - Since
`7`

is greater than`5`

, adjust`low`

to`mid + 1 = 3`

. - Compute the new
`mid = (3 + 5) // 2 = 4`

. The middle element is`9`

. - Since
`7`

is less than`9`

, adjust`high`

to`mid - 1 = 3`

. - Compute the new
`mid = (3 + 3) // 2 = 3`

. The middle element is`7`

. `7`

is equal to the middle element, so the target is found at index`3`

.

### Code Examples

#### 1. Python

```
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # Target not found
# Example usage
arr = [1, 3, 5, 7, 9, 11]
target = 7
index = binary_search(arr, target)
print(f"Target found at index: {index}")
```

#### 2. JavaScript

```
function binarySearch(arr, target) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // Target not found
}
// Example usage
const arr = [1, 3, 5, 7, 9, 11];
const target = 7;
const index = binarySearch(arr, target);
console.log(`Target found at index: ${index}`);
```

#### 3. Java

```
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // Target not found
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11};
int target = 7;
int index = binarySearch(arr, target);
System.out.println("Target found at index: " + index);
}
}
```

#### 4. C++

```
#include <iostream>
#include <vector>
int binarySearch(const std::vector<int>& arr, int target) {
int low = 0;
int high = arr.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // Target not found
}
int main() {
std::vector<int> arr = {1, 3, 5, 7, 9, 11};
int target = 7;
int index = binarySearch(arr, target);
std::cout << "Target found at index: " << index << std::endl;
return 0;
}
```

#### 5. C

```
using System;
class Program {
public static int BinarySearch(int[] arr, int target) {
int low = 0;
int high = arr.Length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // Target not found
}
static void Main() {
int[] arr = {1, 3, 5, 7, 9, 11};
int target = 7;
int index = BinarySearch(arr, target);
Console.WriteLine("Target found at index: " + index);
}
}
```

To implement binary search:

**Initialize**`low`

and`high`

pointers.**Calculate**the middle index and compare the target with the middle element.**Adjust**the search range based on the comparison.**Repeat**until the target is found or the range is exhausted.

The provided code in Python, JavaScript, Java, C++, and C# illustrates how to implement these steps and find the target value efficiently.