Count occurrences of a number in a sorted array with duplicates using binary search

Question

0.00/5 (No votes)

See more:

Hello

Following the following youtube video, I am trying to use the given algorithm to trace how many times 5 appears in this array

[1][1][3][3][5][5][5][5][5][9][9][11]

the algorithm is

C++

findCount(a, n, x, searchfirst){

low = 0;
high = n-1;
result = -1;

while (low <= high){

mid = (low+high)/2;

    if(a[mid] ==x){
     result = mid;

    if(searchfirst){
     high = mid-1;

    }else{
      low = mid+1;

    }


    }

    else if (x < a[mid]) high = mid -1;
    else low = mid +1;
  }

return result


}

fyi, running the code is not important. the purpose is to be able to trace the instructions in the algorithm and reach the answer

Here is the original video:
Count occurrences of a number in a sorted array with duplicates using Binary Search - YouTube[^]

What I have tried:

When I trace it, I get

low    high    mid  a[mid] result
    0        11    5    5       5
    0        4     2    3
    3        4     3    3
    4        4     4    5       4
    4        3

this is where I am stuck, my last mid is at index 4 (this is lowest occurrence index of 5)
I should change high to mid -1 so 4-1 = 3; low is 4 high is 3 but the while says (low <=high) 4<3 is false, so I cant reenter this while loop to now look for the highest occurence of 5 with the else{low = mid+1;}. Where did I go wrong in copying this algorithm.

Also, can you tell me how the flag search suppose to help in this code.

Posted 29-Oct-17 10:02am

mappleleaf

Updated 29-Oct-17 15:35pm

Patrice T

v3

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2017-10-29T15:35:00

Learn to indent properly your code, it show its structure and it helps reading and understanding.

C++

findCount(a, n, x, searchfirst){

  low = 0;
  high = n-1;
  result = -1;

  while (low <= high){
    mid = (low+high)/2;
    if(a[mid] ==x){
      result = mid;
      if(searchfirst){
        high = mid-1;
      }else{
        low = mid+1;
      }
    }
    else if (x < a[mid])
      high = mid -1;
    else
      low = mid +1;
  }
  return result
}

Professional programmer's editors have this feature and others ones such as parenthesis matching and syntax highlighting.
Notepad++ Home[^]
ultraedit[^]
[Update]

Quote:
I dont understand the purpose of searchfirst

There is a tool that allow you to see what your code is doing, its name is debugger. It is also a great learning tool because it show you reality and you can see which expectation match reality.
When you don't understand what your code is doing or why it does what it does, the answer is debugger.
Use the debugger to see what your code is doing. Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.