使用二进制搜索计算带有重复项的已排序数组中的数字的出现次数 [英] Count occurrences of a number in a sorted array with duplicates using binary search
问题描述
你好
按照以下youtube视频，我试图用给定的算法追踪5在这个数组中出现的次数
[1] [1] [3] [3] [5] [5] [5] [5] [5] [9] [9] [11]
算法是
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
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，运行代码并不重要。目的是能够追踪算法中的指令并得出答案
这是原始视频：
使用二进制搜索计算带有重复项的已排序数组中某个数字的出现次数 - YouTube [ ^ ]
我尝试了什么：
当我追踪它时，我得到了
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
这是我被困的地方，我的最后一次mid是指数4（这是5的最低发生指数）
我应该从高到中改变-1所以4-1 = 3;低是4高是3但是虽然说（低< =高）4< 3是假的，所以我不能重新进入这个循环现在寻找5的最高出现与else {low = mid + 1;} 。我在复制这个算法时出了什么问题。
另外，你能告诉我旗帜搜索在这段代码中如何帮助。
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.
推荐答案
学会正确地缩进你的代码，它显示它的结构，它有助于阅读和理解。
Learn to indent properly your code, it show its structure and it helps reading and understanding.
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
}
专业程序员的编辑有这个功能和其他功能，如括号匹配和语法突出显示。
Notepad ++ Home [ ^ ]
ultraedit [ ^ ]
[更新]
Professional programmer's editors have this feature and others ones such as parenthesis matching and syntax highlighting.
Notepad++ Home[^]
ultraedit[^]
[Update]
我不明白searchfirst的目的
I dont understand the purpose of searchfirst
有一个工具可以让你看到你的代码在做什么，它的名字是调试器。它也是一个很好的学习工具，因为它向你展示了现实，你可以看到哪种期望与现实相符。
当你不明白你的代码在做什么或为什么它做它做的时候，答案就是答案是调试器。
使用调试器查看代码正在执行的操作。只需设置断点并查看代码执行情况，调试器允许您逐行执行第1行并在执行时检查变量。
调试器 - 维基百科，免费的百科全书 [ ^ ]
调试器在这里向您展示您的代码正在做什么，您的任务是与它应该做什么进行比较。
调试器中没有魔法，它没有发现错误，它只是帮助你。当代码没有达到预期的效果时，你就会接近一个错误。
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.
这篇关于使用二进制搜索计算带有重复项的已排序数组中的数字的出现次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
