Can you say that again?

Requirements

• The array must be sorted
• Must know the value to search for
• If the value is not found in the data set, then return -1.
• If the value is found, then return the index at where the value occurs in the data set.

Iterative Version (JavaScript)

function binarySearch(data, key) {
    let start = 0;
    let end = data.length - 1;
    
    while (start <= end) {
        const mid = Math.trunc((end - start) / 2) + start;
        
        if (data[mid] === key) {
            return mid;
        } else if (data[mid] > key) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    
    return -1;
}

Gotchas

• Math.trunc to convert the midpoint to integer.
• Continue to iterate as long as start is less than or equal to end.

Test 1

const data = [];
const occurrence = binarySearch(data, 1);

console.log(occurrence); // -1

Test 2

const data = [2, 5, 7, 8];
const occurrence = binarySearch(data, 4);

console.log(occurrence); // -1

Test 3

const data = [2, 5, 7, 8, 9, 10];
const occurrence = binarySearch(data, 9);

console.log(occurrence); // 4

Recursive Version (JavaScript)

function binarySearch(data, key) {
    return binarySearchRecursiveInner(data, key, 0, data.length - 1);
    
    function binarySearchRecursiveInner(data, key, start, end) {
        if (start > end) {
            return - 1;
        }
        
        const mid = Math.trunc((end - start) / 2) + start;
        
        if (data[mid] === key) {
            return mid;
        }
        
        if (data[mid] > key) {
            return binarySearchRecursiveInner(data, key, start, mid - 1);
        } else {
            return binarySearchRecursiveInner(data, key, mid + 1, end);
        }
    }
}

The base case mirrors that of the stopping condition of the while loop of the iterative version.

An inner function called binarySearchRecursiveInner is used to keep the public API simple. It is the main recursive function. binarySearch is kept to allow separation of concerns between implementation choice and purpose.