**Algorithm Name**:Binary Search

* **Questions**:
Is the input array sorted? Can the array contain duplicate values?
If yes, do we want to return the first occurrence, the last occurrence, or any occurrence of the target?
Note: For simplicity, the following implementation assumes that the array is sorted in ascending order and does not contain duplicate values.

* **Time Complexity**:
- Both Brute Force and Optimized: O(log n) where n is the size of the array.
The algorithm halves the size of the array in each iteration.

* **Space Complexity**:
- Both Brute Force and Optimized: O(1) as no extra space is required.
We are only using a few integer variables.

* **Approaches**: - Optimized: Initialize two pointers, left and right, to the start and end of the array respectively. Then, in a loop, calculate the middle element. If the target is equal to the middle element, return the middle index. If the target is less than the middle element, move the right pointer to middle - 1. If the target is greater than the middle element, move the left pointer to middle + 1. Continue this process until the left pointer is less than or equal to the right pointer or the target is found. * **Explanation**:
The Binary Search algorithm works by dividing the array into two halves and determining which half the target is likely to be in.
This allows us to discard half of the elements in each iteration.
This is why binary search is much faster than linear search in a sorted array.

* **Sample Code**:javascript

function binarySearch(arr, target) {
let left = 0; // Start pointer
let right = arr.length - 1; // End pointer
while (left <= right) {
let middle = Math.floor((left + right) / 2); // Calculate middle index
if (arr[middle] === target) { // If target is found at the middle index return middle;
}
if (arr[middle] < target) {
// If target is greater than middle, move left pointer to middle + 1
left = middle + 1;
} else { // If target is less than middle, move right pointer to middle - 1
right = middle - 1;
}
}
return -1; // If target is not found, return -1
}

// Unit test
console.log(binarySearch([1, 2, 3, 4, 5, 6], 4)); // Output is 3
console.log(binarySearch([1, 2, 3, 4, 5, 6], 7)); // Output is -1 because 7 is not
- Input: arr = [1, 2, 3, 4, 5, 6], target = 4
- Output: 3 which is the index of target in the array