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

lllaaa 发表于 2005-9-29 19:02

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) return middle;
 if(x > a) left = middle;
 else right = middle;
}//while
return –1;
}
 <o:p></o:p>
 <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) right = middle;
 else left = middle;
}//while
if(x == a) return left;
else return –1;
}
 <o:p></o:p>
 <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) 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)
 {
 int left = 0, right = n-1;
 while(left < right)
 {
 int middle = (left + right) / 2;
if(x < a) 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)
 {
 int left = 0, right = n-1;
 while(left < right)
 {
 int middle = (left + right + 1) / 2;
if(x < a) 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)
 {
 int left = 0, right = n-1;
 while(left < right)
 {
 int middle = (left + right + 1) / 2;
if(x < a) 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)
 {
 int left = 0, right = n-1;
 while(left < right)
 {
 int middle = (left + right +1) / 2;
if(x < a) 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) 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 且 a ≠ a成立，则必将在某一步之后出现x = a，导致永远不会出现x = a的情形，算法最终在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条件成立时，即必然进入死循环。<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且left < right，<o:p></o:p>
∴middle = (left + right + 1) / 2 = / 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成立时，再执行if 语句中的<o:p></o:p>
left = middle + 1;<o:p></o:p>
就把结果丢失了，导致错误。而且还可能会导致下标越界错误。例如：<o:p></o:p>
当n = 2且x = a时即会出现这些情况。<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，则必进入死循环。<o:p></o:p>
原因：right值的修改不正确。<o:p></o:p>

页: [1]

数学建模社区-数学中国's Archiver

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