Finding first and last occurence of an element in a sorted array in O(logn) using binary search recursively

Viewed 39

I am doing a leetcode question [34][1]

I came up with a solution

 function firstAndLastOccurenceOfElement(arr, key, start, end){

    let mid = Math.floor((start + end)/2)
    if(start > end){
        return -1;
    }
    if(arr[mid] === key){
        firstOccurence = mid;
        lastOccurence = mid;
        let checkFirstOccurence = firstAndLastOccurenceOfElement(arr, key,start, mid -1)
        if(checkFirstOccurence < firstOccurence){
            firstOccurence =checkFirstOccurence
        }
        let checkLastOccurence = firstAndLastOccurenceOfElement(arr, key,mid +1, end)
        if(checkLastOccurence > lastOccurence){
            lastOccurence = checkLastOccurence
        }
        return [firstOccurence, lastOccurence]
    }
    if(arr[mid] > key){
        return firstAndLastOccurenceOfElement(arr, key, start, mid - 1)
    }
    if(arr[mid] < key){
        return firstAndLastOccurenceOfElement(arr, key, mid + 1 , end)
    }
    return -1;
}

let arr = [2, 5, 5, 5, 6, 6, 8, 9, 9, 9];
let key = 5;
console.log(firstAndLastOccurenceOfElement(arr, key, 0, arr.length - 1));

But this somehow doesn't find the first index. For the above input it gives something like :

[-1, 3]

I tried debugging but it didn't really give me much. What's wrong here? [1]: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

0 Answers
Related