我如何...编写程序进行二分查找 [英] How do i...write a program to do binary search
问题描述
开发一个程序来实现二进制搜索算法。此技术比较排序后的中间元素的搜索键值。然后;
（a）如果匹配，则搜索结束。
（b）如果搜索键值小于中间值，那么前半部分list包含键值。
（c）如果搜索键值大于中间值，则后半部分包含键值。
重复此分而治之策略，直到我们有比赛。如果列表缩小为一个不匹配的元素，则列表不包含键值。
测试案例1
INPUT
10 11 12 13 1 3 2 4 7 8 110 122 123
2
OUTPUT
该商品在列表中，其位置= 7
< b>我尝试了什么：
#include < stdio.h >
main（）
{
int top，bottom，middle ， value [ 50 ]，key，n，i;
clrscr（）;
printf（ 输入数组中元素的数量：）;
scanf（ ％d，& n）;
printf（ 按升序输入数组元素\ n）;
for （i = 1 ; i< = n; i ++）
scanf （ ％d，& value [i]）;
printf（ 输入您要搜索的值：）;
scanf（ ％d，& key）;
top = n- 1 ;
bottom = 0 ;
做
{
middle =（top + bottom）/ 2;
if （ value [middle]< key）
bottom = middle + 1;
else
top = middle;
}
while （top> bottom）;
if （top == - 1 ）
printf（ 列表为空！）;
else if （ value [top] == key）
printf（ 已找到值！）;
else
printf（ 目标价值尚未找到！）;
getch（）;
return 0 ;
}
好消息：实施看起来是正确的。在我看来，有一个小缺陷：
Quote：for（i = 1; i< = n; i ++）
应该是
for （i = 0 ; i< n; i ++）
此外它可能会更好地报告找到的项目的位置，即替换Quote：printf（已找到值！）;
printf（ 已找到值位置％d，（顶部+ 1））;
坏消息：测试用例完全错误（编号必须按升序排列）。
建议：首先正确缩进代码，显示结构并帮助阅读。
专业程序员的编辑器具有这样的功能以及对程序员有用的其他功能s。
Notepad ++ Home [ ^ ]
UltraEdit |原始文本编辑器 [ ^ ]
#include < stdio.h >
main（）
{
int top，bottom，middle， value [ 50 ]，键，N，I;
clrscr（）;
printf（ 输入数组中元素的数量：）;
scanf（ ％d，& n）;
printf（ 按升序输入数组元素\ n）;
for （i = 1 ; i< = n; i ++）
scanf （ ％d，& value [i]）;
printf（ 输入您要搜索的值：）;
scanf（ ％d，& key）;
top = n- 1 ;
bottom = 0 ;
做
{
middle =（top + bottom）/ 2;
if （ value [middle]< key）
bottom = middle + 1;
else
top = middle;
}
while （top> bottom）;
if （top == - 1 ）
printf（ 列表为空！）;
else if （ value [top] == key）
printf（ 已找到值！）;
else
printf（ 目标价值尚未找到！）;
getch（）;
return 0 ;
}
二分法搜索 - 维基百科 [< a href =https://en.wikipedia.org/wiki/Dichotomic_searchtarget =_ blanktitle =New Window> ^ ]
-----
有一个工具可以让你看到你的代码在做什么，它的名字是调试器。它也是一个很好的学习工具，因为它向你展示了现实，你可以看到哪种期望与现实相符。
当你不明白你的代码在做什么或为什么它做它做的时候，答案就是答案是调试器。
使用调试器查看代码正在执行的操作。只需设置断点并查看代码执行情况，调试器允许您逐行执行第1行并在执行时检查变量。
调试器 - 维基百科，免费的百科全书 [ ^ ]
掌握Visual Studio 2010中的调试 - 初学者指南 [ ^ ]
使用Visual Studio 2010进行基本调试 - YouTube [ ^ ]
调试器在这里向您展示您的代码正在做什么，您的任务是与什么进行比较应该这样做。
调试器中没有魔法，它没有找到错误，它只是帮助你。当代码没有达到预期的效果时，你就会接近一个错误。
Develop a program to implement the binary search algorithm. This technique compares the search key value of the element that is midway in a sorted lies. Then ;
(a) If they match, the search is over.
(b) If the search key value is less than the middle value, then the first half of list contains the key value.
(c) If the search key value is greater than the middle value, then the second half contains the key value.
Repeat this divide and-conquer strategy until we have match. If the list is reduced to one non-matching element, then the list does not contain the key value.
TEST CASE 1
INPUT
10 11 12 13 1 3 2 4 7 8 110 122 123
2
OUTPUT
The item is in the list and its position is=7
What I have tried:
#include <stdio.h>
main()
{
int top,bottom,middle,value[50],key,n,i;
clrscr();
printf("Enter the number of elements in array:");
scanf("%d",&n);
printf("Enter the elements of array in ascending order\n");
for(i=1;i<=n;i++)
scanf("%d",&value[i]);
printf("Enter the value which you want to search:");
scanf("%d",&key);
top=n-1;
bottom=0;
do
{
middle=(top+bottom)/2;
if(value[middle]<key)
bottom=middle+1;
else
top=middle;
}
while(top>bottom);
if(top==-1)
printf("List is empty!");
else if(value[top]==key)
printf("value has been found!");
else
printf("Target value has not been found!");
getch();
return 0;
}The good news: the implementation looks correct. Well there is a minor flaw, in my opinion:
Quote:for(i=1;i<=n;i++)
should be instead
for(i=0;i<n;i++)
Moreover it would probably be better reporting the position of the found item, i.e. replaceQuote:printf("value has been found!");
with
printf("value has been found at position %d", (top+1));
The bad news: the test case is completely wrong (number must be in ascending order).
Advice: Start by indenting properly your code, it show the structure and helps reading.
Professional programmer's editors have such feature along with other ones useful to programmers.
Notepad++ Home[^]
UltraEdit | The Original Text Editor[^]
#include <stdio.h> main() { int top,bottom,middle,value[50],key,n,i; clrscr(); printf("Enter the number of elements in array:"); scanf("%d",&n); printf("Enter the elements of array in ascending order\n"); for(i=1;i<=n;i++) scanf("%d",&value[i]); printf("Enter the value which you want to search:"); scanf("%d",&key); top=n-1; bottom=0; do { middle=(top+bottom)/2; if(value[middle]<key) bottom=middle+1; else top=middle; } while(top>bottom); if(top==-1) printf("List is empty!"); else if(value[top]==key) printf("value has been found!"); else printf("Target value has not been found!"); getch(); return 0; }
Dichotomic search - Wikipedia[^]
-----
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[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]
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屋！
