/*
const list: number[] = []

for(let i = 1; i<=111002; i++){
    list.push(i)
}
const start = Date.now()
*/

// Main Search Function
export const binarySearch = (array: number[], item: number, baseIndex: number = 0): number | null=>{
    if(!array.length){ return null};
    if(array.length === 1){
        if(array[0] === item){ return baseIndex + 0};
        return null;
    };
    const middle: number = (array.length-1)/2;

    // Next Recursive Call
    let newArr: number[] | null = null;
    let next: 0 | 1 | 2 = 0;
    let nextBaseIndex: number = baseIndex;

    // Input Count
    if(Number.isInteger(middle)){
        // Odd Count of Inputs
        const middleItem: number = array[middle];
        if(middleItem === item){ return baseIndex + middle};
        
        if(item < middleItem){
            next = 1
            newArr = array.slice(0, middle)
            nextBaseIndex = baseIndex;
        } else {
            next = 2
            newArr = array.slice(middle+1, array.length)
            nextBaseIndex = baseIndex+middle+1;
        };
    } else {
        // Even Count of Inputs
        const middleLeft: number = Math.floor(middle);
        const middleRight: number =  Math.ceil(middle);
        const middleLeftItem: number = array[middleLeft];
        const middleRightItem: number = array[middleRight];
        if(middleLeftItem === item){ return baseIndex + middleLeft};
        if(middleRightItem === item){ return baseIndex + middleRight};
        
        if(item < middleLeftItem){
            next = 1
            newArr = array.slice(0, middleLeft)
            nextBaseIndex = baseIndex;
        } else {
            next = 2
            newArr = array.slice(middleLeft+1, array.length)
            nextBaseIndex = baseIndex+middleLeft+1;
        };
    }

    // Internal Errors
    if(!next){ throw new Error("Next Recursive Side Invalid")}
    if(!newArr){ throw new Error("newArr is NULL")}

    // Recursive Call
    return binarySearch(newArr, item, nextBaseIndex)
}
/*
const find: number = 100002;
console.log(list)
console.log("Item to Find", find)
const findIndex: number | null = binarySearch(list, find)
console.log(`Time Taken: \x1b[32m${Date.now() - start}ms\x1b[0m`)
console.log(findIndex? `✅ Found \x1b[32m${findIndex}\x1b[0m`: `❌ Not Found \x1b[31m${findIndex}\x1b[0m`)
*/