算法设计与分析第4版课后习题第二章第2小题
目录
《算法设计与分析（第4版）》课后习题第二章第2小题
《算法设计与分析（第4版）》课后习题第二章第2小题
下面的7个算法与本章中的二分搜索算法binarySearch略有不同。请判断这7个算法的正确性，并说明原因和证明。
第二章二分搜索算法binarySearch代码如下：
public static int binarySearch1(int []a,int x,int n){
int left = 0;int right = n-1;
while(left<=right){
int middle = (left+right)/2;
if(x==a[middle]) return middle;
if(x>a[middle]) left= middle-1;
else right = middle;
}
return -1;
}算法一：
public static int binarySearch1(int []a,int x,int n){
int left = 0;int 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;
}
return -1;
}与上面的binarySearch相比在if判断语句后，left和right所对应指针并没有得到很好的调整，从而导致在搜索比数组中的最大值或者不在数组中的值时，会陷入死循环。运行代码如下：
public class BinarySearch {
public static int binarySearch1(int []a,int x,int n){
int left = 0;int 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;
}
return -1;
}
public static void main(String[] args) {
int []a= {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n=a.length;
int x=-91;
int num = binarySearch1(a,x,n);
if (num==-1)
System.out.println("没有找到该元素");
else
System.out.println("该元素位于数组的第"+(num+1)+"个");
}
}算法二：
public static int binarySearch2(int []a,int x,int n){
int left = 0;int right = n-1;
while(left<right-1){
int middle = (left+right)/2;
if(x<a[middle]) right = middle;
else left = middle;
}
if (x==a[left]) return left;
else return -1;
}与上面的binarySearch相比在，数组段中的left与right游标调整不正确，导致x==a[n-1]时返回错误，也就是说，拿数组中的最大值去数组中搜索，是搜索不到的。运行代码如下：
public static int binarySearch2(int []a,int x,int n){
int left = 0;int right = n-1;
while(left<right-1){
int middle = (left+right)/2;
if(x<a[middle]) right = middle;
else left = middle;
}
if (x==a[left]) return left;
else return -1;
}
public static void main(String[] args) {
int []a= {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n=a.length;
int x=9;
int num = binarySearch2(a,x,n);
if (num==-1)
System.out.println("没有找到该元素");
else
System.out.println("该元素位于数组的第"+(num+1)+"个");
}算法3：
public static int binarySearch3(int []a,int x,int n){
int left = 0;int right = n-1;
while(left+1!=right){
int middle = (left+right)/2;
if(x>=a[middle])left = middle;
else right = middle;
}
if ((x==a[left]))return left;
else return -1;
}与正确算法中binarySearch5相比，数组中左右游标left和right的调整不正确，导致x==a[n-1]是返回错误，也就是说，该程序搜索最大值时，会显示找不到对象。运行代码如下：
public static int binarySearch3(int []a,int x,int n){
int left = 0;int right = n-1;
while(left+1!=right){
int middle = (left+right)/2;
if(x>=a[middle])left = middle;
else right = middle;
}
if ((x==a[left]))return left;
else return -1;
}
public static void main(String[] args) {
int []a= {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n=a.length;
int x=1;
int num = binarySearch3(a,x,n);
if (num==-1)
System.out.println("没有找到该元素");
else
System.out.println("该元素位于数组的第"+(num+1)+"个");
}算法4：
public static int binarySearch4(int []a,int x,int n){
if (n>0&&x>=a[0]){
int left = 0;int right = n-1;
while(left<right){
int middle = (left+right)/2;
if(x<a[middle])right = middle-1;
else left = middle;
}
if ((x==a[left]))return left;
}
return -1;
}与正确算法中的binarySearch5相比，数组中左右游标left和right的调整不正确，在while语句中middle的值会重复地赋值给left，在搜索一些值时会陷入死循环。运行代码如下：
public static int binarySearch4(int []a,int x,int n){
if (n>0&&x>=a[0]){
int left = 0;int right = n-1;
while(left<right){
int middle = (left+right)/2;
if(x<a[middle])right = middle-1;
else left = middle;
}
if ((x==a[left]))return left;
}
return -1;
}
public static void main(String[] args) {
int []a= {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n=a.length;
int x=3;
int num = binarySearch4(a,x,n);
if (num==-1)
System.out.println("没有找到该元素");
else
System.out.println("该元素位于数组的第"+(num+1)+"个");
}算法5：
public static int binarySearch5(int []a,int x,int n){
if (n>0&&x>=a[0]){
int left = 0;int right = n-1;
while(left<right){
int middle = (left+right+1)/2;
if(x<a[middle])right = middle-1;
else left = middle;
}
if ((x==a[left]))return left;
}
return -1;
}算法正确，且当数组中有重复元素时，返回满足条件的最右元素。运行代码如下：
public static int binarySearch5(int []a,int x,int n){
if (n>0&&x>=a[0]){
int left = 0;int right = n-1;
while(left<right){
int middle = (left+right+1)/2;
if(x<a[middle])right = middle-1;
else left = middle;
}
if ((x==a[left]))return left;
}
return -1;
}
public static void main(String[] args) {
int []a= {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n=a.length;
int x=5;
int num = binarySearch5(a,x,n);
if (num==-1)
System.out.println("没有找到该元素");
else
System.out.println("该元素位于数组的第"+(num+1)+"个");
}
}算法6：
public static int binarySearch6(int []a,int x,int n){
if (n>0&&x>=a[0]){
int left = 0;int right = n-1;
while(left<right){
int middle = (left+right+1)/2;
if(x<a[middle])right = middle-1;
else left = middle+1;
}
if ((x==a[left]))return left;
}
return -1;
}与正确算法中binarySearch5相比，数组中左右游标left和right的调整不正确，导致该搜索值不是首尾元素，或者进行二分法后的首尾元素时就会返回错误，例如数组{1,2，3,4，5,6，7,8，9}中，就只有1,4，6,9能被搜索到，运行代码如下：
public static int binarySearch6(int []a,int x,int n){
if (n>0&&x>=a[0]){
int left = 0;int right = n-1;
while(left<right){
int middle = (left+right+1)/2;
if(x<a[middle])right = middle-1;
else left = middle+1;
}
if ((x==a[left]))return left;
}
return -1;
}
public static void main(String[] args) {
int []a= {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n=a.length;
int x=8;
int num = binarySearch6(a,x,n);
if (num==-1)
System.out.println("没有找到该元素");
else
System.out.println("该元素位于数组的第"+(num+1)+"个");
}算法7：
public static int binarySearch7(int []a,int x,int n){
if (n>0&&x>=a[0]){
int left = 0;int right = n-1;
while(left<right){
int middle = (left+right+1)/2;
if(x<a[middle])right = middle;
else left = middle;
}
if ((x==a[left]))return left;
}
return -1;
}与正确算法中binarySearch5相比，数组中左右游标left和right的调整不正确，导致在判断x与middle的大小时陷入死循环。根据运行结果就只能搜索该数组的最大值，运行代码如下：
public static int binarySearch7(int []a,int x,int n){
if (n>0&&x>=a[0]){
int left = 0;int right = n-1;
while(left<right){
int middle = (left+right+1)/2;
if(x<a[middle])right = middle;
else left = middle;
}
if ((x==a[left]))return left;
}
return -1;
}
public static void main(String[] args) {
int []a= {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n=a.length;
int x=8;
int num = binarySearch7(a,x,n);
if (num==-1)
System.out.println("没有找到该元素");
else
System.out.println("该元素位于数组的第"+(num+1)+"个");
}