Click here to Skip to main content
15,559,275 members
Please Sign up or sign in to vote.
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
Updated 29-Oct-17 16:35pm
v3

1 solution

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.
 
Share this answer
 
v2
Comments
mappleleaf 30-Oct-17 5:11am    
Thank you for indenting my code, but I am still not sure of how to trace it to get the total number of occurrence of 5 and I dont understand the purpose of searchfirst

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900