查看: 2817|回复: 0

[讨论]一道分治法的题目，仅供参考

字体大小: 正常放大

lllaaa

2 主题	2 听众	27 积分

升级 23.16%

该用户从未签到

电梯直达

1^#

发表于 2005-9-29 19:02 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

<

>2-2、下面的7个算法与本章中的二分搜索算法binarySearch略有不同。请判断这7个算法的正确性。如果算法不正确，请说明错误产生的原因。如果算法正确，请给出算法的正确性证明。
<

>public static int binarySearch1(int[] a, int x, int n)
<

>{
<

> int left = 0, right = n-1;
<

> while(left <= right)
<

>{
<

> int middle = (left + right) / 2;
<

> if(x == a[middle]) return middle;
<

> if(x > a[middle]) left = middle;
<

> else right = middle;
<

>}//while
<

>return –1;
<

>}
<

> <o:p></o:p>
<

>public static int binarySearch2(int[] a, int x, int n)
<

>{
<

> int left = 0, right = n-1;
<

> while(left < right-1)
<

>{
<

> int middle = (left + right) / 2;
<

> if(x < a[middle]) right = middle;
<

> else left = middle;
<

>}//while
<

>if(x == a

) return left;
<

>else return –1;
<

>}
<

> <o:p></o:p>
<

>public static int binarySearch3(int[] a, int x, int n)
{
 int left = 0, right = n-1;
 while(left+1 != right)
{
 int middle = (left + right) / 2;
 if(x >= a[middle]) left = middle;
 else right = middle;
}//while
if(x == a

) return left;
else return –1;
}
 <o:p></o:p>
 <o:p></o:p>
public static int binarySearch4(int[] a, int x, int n)
{
 if(n > 0 && x >= a[0])
 {
 int left = 0, right = n-1;
 while(left < right)
 {
 int middle = (left + right) / 2;
if(x < a[middle]) right = middle - 1;
else left = middle;
}//while
if(x == a

) return left;
}//if
return –1;
}
 <o:p></o:p>
 <o:p></o:p>
public static int binarySearch5(int[] a, int x, int n)
{
 if(n > 0 && x >= a[0])
 {
 int left = 0, right = n-1;
 while(left < right)
 {
 int middle = (left + right + 1) / 2;
if(x < a[middle]) right = middle - 1;
else left = middle;
}//while
if(x == a

) return left;
}//if
return –1;
}
 <o:p></o:p>
 <o:p></o:p>
public static int binarySearch6(int[] a, int x, int n)
{
 if(n > 0 && x >= a[0])
 {
 int left = 0, right = n-1;
 while(left < right)
 {
 int middle = (left + right + 1) / 2;
if(x < a[middle]) right = middle - 1;
else left = middle + 1;
}//while
if(x == a

) return left;
}//if
return –1;
}
 <o:p></o:p>
 <o:p></o:p>
public static int binarySearch7(int[] a, int x, int n)
{
 if(n > 0 && x >= a[0])
 {
 int left = 0, right = n-1;
 while(left < right)
 {
 int middle = (left + right +1) / 2;
if(x < a[middle]) right = middle;
else left = middle;
}//while
if(x == a

) return left;
}//if
return –1;
}
 <o:p></o:p>
解：（1）算法1不正确。<o:p></o:p>
当在数组a中找不到与x相等的元素时，算法将进入死循环状态。<o:p></o:p>
原因：每次循环时，变量left和right的值修改不正确。应修改如下：<o:p></o:p>
if(x > a[middle]) left = middle + 1;<o:p></o:p>
 else right = middle - 1;<o:p></o:p>
（2）算法2不正确。<o:p></o:p>
当n≥2时，如果条件x = a[n-1] 且 a[n-2] ≠ a[n-1]成立，则必将在某一步之后出现x = a[left +1]，导致永远不会出现x = a[middle]的情形，算法最终在x = a

时结束循环，导致错误地返回-1。<o:p></o:p>
另外，当n=0时执行if(x == a

)...时将出现下标越界错误。<o:p></o:p>
原因：循环结束条件错误，应改为left <= right。每次循环时，变量left和right的值修改也不正确。<o:p></o:p>
（3）算法3不正确。<o:p></o:p>
除了有与算法2相同的错误，另外当n=0或n=1时，必然进入死循环。<o:p></o:p>
原因：与算法2相同。<o:p></o:p>
（4）算法4不正确。<o:p></o:p>
如果在循环过程中出现left = right – 1情况，算法即进入死循环。例如 x≥a[n-2]条件成立时，即必然进入死循环。<o:p></o:p>
原因：循环条件和对变量left值的修改有错误。<o:p></o:p>
（5）此算法正确。<o:p></o:p>
证明：当n=0或n=1时，算法显然正确。<o:p></o:p>
当n≥2时，在循环结束前有x≥a[0]且left < right，<o:p></o:p>
∴middle = (left + right + 1) / 2 = [left + (right –1) + 1 +1] / 2 ≥ (2left + 2) / 2 = left + 1，<o:p></o:p>
即：middle > left成立。<o:p></o:p>
且middle = (left + right + 1) / 2 = [(left + 1) + right] / 2 ≤ 2right / 2 = right，<o:p></o:p>
∴left < middle ≤ right恒成立。<o:p></o:p>
因此，每次循环之后，right与left之差必然减小，在有限次循环后，必有left = right条件成立，从而循环结束。<o:p></o:p>
如果x值与数组a的某个元素值相等，则在循环结束时显然有x = a

且x = a

成立，否则x ≠a

,即未找到x，<o:p></o:p>
∴返回结果正确。<o:p></o:p>
（6）算法6是错误的。<o:p></o:p>
当执行到某次循环x = a[middle]成立时，再执行if 语句中的<o:p></o:p>
left = middle + 1;<o:p></o:p>
就把结果丢失了，导致错误。而且还可能会导致下标越界错误。例如：<o:p></o:p>
当n = 2且x = a[1]时即会出现这些情况。<o:p></o:p>
原因：if 语句中的left = middle + 1;应改为left = middle;<o:p></o:p>
（7）算法7是错误的。<o:p></o:p>
在循环过程中，一旦出现<o:p></o:p>
a

≤ x < a[left + 1]，则必进入死循环。<o:p></o:p>
原因：right值的修改不正确。<o:p></o:p>

zan