Binary search is a powerful algorithm used to efficiently find the position of a target value within a sorted array or list. Its effectiveness lies in its ability to eliminate half of the remaining elements in each step, resulting in a logarithmic time complexity of O(log n), where n is the number of elements in the array.

Let’s break down how binary search works and provide a practical example in JavaScript.

### How Binary Search Works

1 – **Initial Setup:**

- Start with a sorted array.
- Set two pointers,
`low`

and`high`

, to the first and last indices of the array.

2 – **Middle Element:**

- Find the middle element of the array:
`mid = Math.floor((low + high) / 2)`

.

3 – **Comparison:**

- Compare the middle element with the target value.

4 – **Three Possible Cases:**

- If the middle element is equal to the target value, the search is successful.
- If the middle element is greater than the target, update
`high`

to`mid - 1`

and search in the left half. - If the middle element is less than the target, update
`low`

to`mid + 1`

and search in the right half.

5 – **Repeat:**

- Repeat steps 2-4 until the target value is found or
`low`

exceeds`high`

.

6 – **Termination:**

- If
`low`

is greater than`high`

, the target value is not in the array.

### Example in JavaScript

Let’s implement a binary search algorithm in JavaScript:

```
function binarySearch(arr, target) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
return mid; // Target found, return the index
} else if (arr[mid] > target) {
high = mid - 1; // Search in the left half
} else {
low = mid + 1; // Search in the right half
}
}
return -1; // Target not found
}
// Example usage:
const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const targetValue = 7;
const result = binarySearch(sortedArray, targetValue);
if (result !== -1) {
console.log(`Target ${targetValue} found at index ${result}.`);
} else {
console.log(`Target ${targetValue} not found in the array.`);
}
```

In this example, we use a `binarySearch`

function to find the index of a target value in a sorted array. The function returns the index if the target is found and -1 otherwise.

Feel free to use this binary search algorithm in your projects when dealing with sorted data. Its efficiency makes it a valuable tool, especially for large datasets. Happy coding!

## Leave a Reply