Using Binary Search to find all Occurence of a number in a sorted array using Javascript

Question

I started learning algorithms in JavaScript recently. I was experimenting with binary search when I came across this question and I have been trying to implement it, but I keep having difficulties. The function takes two parameters(a sorted array and a number) and returns an object containing the occurrence and count of the number. The occurrence I'm getting is not the right occurrence of the number, and the count is constant.

This is what I have done so far:

function binarySearchOccurrence(array, element) {
    //declare the start index on the left side to zero
      let startIndex = 0;

      //declare the end index on the right side to the length of array minus 1
      let endIndex = array.length - 1;

      //set initial count to zero
      let count = 0;
      let occurrence = 0;

      //declare an empty object to hold the result of search and count 
      const result = {}

      //Applying binary search, iterate while start does not meed end
     while(startIndex <= endIndex){
          //find the middile index
          let middle = Math.floor((startIndex + endIndex)/2); 
              let guessElement = array[middle];
              count++;
              //if element is present in the middle, increment occurence
          if(guessElement === element){
                  occurrence++;

            while(startIndex <= endIndex){

                if(guessElement > element){
                    endIndex = middle - 1;
                    occurrence++;
                    break;

                } else {
                    startIndex = middle + 1;
                    occurrence++;
                    break;
                } 
            } 

              //Else look in the left or right side accordingly
          } else if (guessElement > element) {
                  endIndex = middle - 1;

          } else {
                  startIndex = middle + 1;
          }
      }
          result.occurrence = occurrence;
          result.count = count;
          return result;
  }

when I test with an array like this: binarySearchOccurrence([1, 2, 3, 4, 4, 4, 5, 5, 5, 6, 7, 8, 9], 5) it returns { occurrence: 6, count: 4 } instead of { occurrence: 3, count: 2 };

What do you mean by `count` and `occurrence`? What does a correct `occurrence` and `count` look like for your example? — lurker, Feb 21 '19 at 11:22
I don't understand why this is so complex. It seems you start in the middle and search both sides of the object. Why not start at the beginning of the object (0) and search until you have reached the end (array.length -1)? — Sablefoste, Feb 21 '19 at 11:22
@Sablefoste I am using binary search method with time complexity of O(logn). — Dan, Feb 21 '19 at 11:26
I guess I still don't understand what method you are referring. What I do see is a second, redundant `while(startIndex <= endIndex){` embedded inside an identical `while(startIndex <= endIndex){`. So it does everything twice. Maybe that is why your results are double your anticipated results. — Sablefoste, Feb 21 '19 at 11:28
@lurker `count` is the number of times my loops runs to find the number. since im using binary search, it should be less. — Dan, Feb 21 '19 at 11:31

kartikay101 · Answer 1 · 2019-02-21T12:19:06.933

Your code repeats the count for each occurrence.

Say we got an array [5,5,5,5], 5. Starting with 0,3 as start,end. Mid=1 so occurrence will become 1 (first if) then inside the while loop, the else part will be calculated so occurrence becomes 2. now you start with 2,3 so mid is 2 which is again counted by the first if statement.

Alternate approach:

Make a binary search function that returns position of element. Run it first time till you find mid say x;
run it again for 0 to x-1 and x+1 to end
Do this until there is no result for first half of search and second half of search
The last known results of the searches can be subtracted to count the number of occurrences.

Example for my approach.

[1, 2, 3, 4, 4, 4, 4, 4, 4, 5, 6, 7, 8]

binarysearch = bs(arr,val,start,end) = returns the position of val in array else -1

pos=bs(arr,val,start,end)
a=pos-1
ppos_a=a
while a!=-1 and a-1>=0:
    ppos_a=a
    a=bs(arr,val,0,a-1)

b=pos+1
ppos_b=b
while b!=-1 and b+1<=len-1:
    ppos_b=b
    b=bs(arr,val,b+1,len-1)

result = ppos_b-ppos_a

This should get you the count. I am a bit doubtful about the complexity but it seems to be c log n where c << n

I wish you could express your ideas using code, maybe I'd understand more. — Dan, Feb 21 '19 at 11:49
I'll add a proper explanation to my approach in the answer, I hope you will be able to write the code for it then, but I don't think it caters to your requirement of log n. It would be some x log n , not sure about the exact complexity though. — kartikay101, Feb 21 '19 at 11:57

Syed Mehtab Hassan · Answer 2 · 2019-02-21T12:56:00.000

Try using this but the complexity will not be O(n) in this case a BST which allows either of the right or left children to be equal to the root node, will require extra computational steps to finish a search where duplicate nodes are allowed. Are duplicate keys allowed in the definition of binary search trees?

function binarySearchOccurrence(array, element) {

      //declare the start index on the left side to zero
      let startIndex = 0;

      //declare the end index on the right side to the length of array minus 1
      let endIndex = array.length - 1;

      //set initial count to zero
      let count = 0;
      let occurrence = 0;

      //declare an empty object to hold the result of search and count 
      const result = {}

      //Applying binary search, iterate while start does not meed end
      while (startIndex <= endIndex) {

        //find the middile index
        let middle = Math.floor((startIndex + endIndex) / 2);
        let guessElement = array[middle];
        count++;

        //if element is present in the middle, increment occurence
        if (guessElement > element) {
          endIndex = middle - 1;
          occurrence++;
        } else if (guessElement < element) {
          startIndex = middle + 1;
          occurrence++;
        } else if (guessElement === element) {
         occurrence++;
         count++;

         let searchleft = middle; // searchleft == middile index

         let searchright = middle;// searchright == middile index


//loop while we donot fine integar < element on left and integar > element on rigth;
          while (array[searchright] == guessElement && array[searchleft] == guessElement ) { 


            if (array[searchright] == element) { //if integar right still equal to element 
              searchright = searchright - 1;
              count++;
              occurrence++;
            } else if(array[searchleft] == element) { //if integar left still equal to element 
            searchleft = searchleft + 1;
              count++;
              occurrence++;
            }
          }
        }
        result.occurrence = occurrence;
        result.count = count;
        return result;
      }}

      console.log(binarySearchOccurrence([1, 2, 3, 4, 4, 4, 5, 5, 5, 6, 7, 8, 9], 5));

your code runs but the `occurrence` is incorrect. it should return 2 instead of 3 — Dan, Feb 21 '19 at 13:04

Prafulla Kumar Sahu · Answer 3 · 2019-06-08T03:33:08.187

This question comes as suggestion in sidebar, while I was looking into some other question, so thought to try it.

I am not a good core JavaScript programmer, but modified your code little bit and I think below code gives you correct result

function binarySearchOccurrence(array, element, flag) {
            //declare the start
            //index on the left side to zero 
            let startIndex = 0; //declare the end index on
            // the right side to the length of array minus 1 
            let endIndex = array.length - 1;
            //set initial count to zero 
            let count = 0;
            let occurence = -1;
            const result = {}
            //Applying binary search, iterate while start does not meed end 
            while (startIndex <= endIndex) { //find the middle index 
                let middle = Math.floor((startIndex + endIndex) / 2);
                count++; //if element is
                //   present in the middle, increment occurence 
                if (array[middle] == element) {
                    occurence = middle;
                    if (flag == "last") {
                        startIndex = middle + 1;
                    } else {
                        endIndex = middle - 1;
                    }
                } else {
                    if (arr[middle] > element) {
                        endIndex = middle - 1;
                    } else {
                        startIndex = middle + 1;
                    }
                }
            }
            result.occurence = occurence;
            result.count = count;
            return result;
        }

        function countOccurence(arr, key) {
            let count = binarySearchOccurrence(arr, key, "last").count + binarySearchOccurrence(arr, key, "first").count;
            let occurence = (binarySearchOccurrence(arr, key, "last").occurence - binarySearchOccurrence(arr, key,
                "first").occurence) + 1;
            let result = {};
            result.occurence = occurence;
            result.count = count;
            return result;
        }
        let arr = [0, 1, 2, 3, 4, 4, 4, 4, 5, 6, 7, 8, 9];
        console.log(countOccurence(arr, 4));

Output in my console

{occurence: 4, count: 8}

Any good JS programmer could edit and make improvement to this code, I will appreciate it.

Using Binary Search to find all Occurence of a number in a sorted array using Javascript

3 Answers3