Question

Java编写程序：排序和查找

给定一个数组:
int a[]={28,39,49,78,23}; // 你可以用任意的测试数据
请对数组中的元素进行排序。

给定一个数字 x=49,
请在排序后的数组中查找该元素。
要求：
* 最好使用折半查找
* 排序和查找自己写函数实现，不要使用标准API。
我编写的源代码如下,请大神帮我看看到底是哪里出错了~~~为什么就是显示不了正确答案呢。。。谢谢了！！！会在线等答案的~~~
public class SortAndSearch{
private int[] A;
public SortAndSearch(int[] arry)
{
int i = 0;
A = new int[arry.length];
for(int value:arry)
{
A[i++] = value;
}
}
public void Sort(int[] a){
int i,j,temp;
for(i=0;i<a.length-1;i++){
for(j=i+1;j<a.length;j++){
if(a[i]>a[j]){
temp = a[i];
a[i] = a[j];
a[j] = temp;
}

}
System.out.print(a[i]+",");
}
temp = a.length-1;
System.out.println(a[temp]);
}
public int Search(int x)
{
int low=0;
int high=A.length;
while(low<=high){
int mid = (low+high)/2;
if(x>A[mid]){
low=mid+1;
}
else if(x<A[mid]){
high=mid-1;
}
else if(x==A[mid]){
return mid;
}
}
return 0;
}
public static void main(String[] args){
int []a={28,39,49,78,23};
SortAndSearch sas = new SortAndSearch(a);
System.out.println("排序前的数组为：28,39,49,78,23");
System.out.print("选择排序后的数组为：");
sas.Sort(a);
System.out.printf("折半查找49记录是%d：",sas.Search(78));
}
}

Answer 1

1. int high = A.length - 1;
2. 你的A数组并没有排序，但是你搜索的是A数组

import java.util.Arrays;

public class SortAndSearch
{
	private int[] A;

	public SortAndSearch ( int[] arry )
	{
		int i = 0;
		A = new int[arry.length];
		for ( int value : arry )
		{
			A[i++] = value;
		}
	}

	public void Sort ( int[] a )
	{
		int i, j, temp;
		for ( i = 0; i < a.length - 1; i++ )
		{
			for ( j = i + 1; j < a.length; j++ )
			{
				if (a[i] > a[j])
				{
					temp = a[i];
					a[i] = a[j];
					a[j] = temp;
				}
			}
			System.out.print (a[i] + ",");
		}
		temp = a.length - 1;
		System.out.println (a[temp]);
	}

	public int Search ( int x )
	{
		int low = 0;
		int high = A.length - 1;
		while (low <= high)
		{
			int mid = ( low + high ) / 2;
			if (x > A[mid])
			{
				low = mid + 1;
			}
			else if (x < A[mid])
			{
				high = mid - 1;
			}
			else
			{
				return mid;
			}
		}
		return -1;
	}

	public static void main ( String[] args )
	{
		int[] a = { 28, 39, 49, 78, 23 };
		SortAndSearch sas = new SortAndSearch (a);
		System.out.println ("排序前的数组为：28,39,49,78,23");
		System.out.print ("选择排序后的数组为：");
		sas.Sort (a);
		System.out.println (Arrays.toString (sas.A));
		int n = 78;
		System.out.printf ("折半查找%d索引是%d", n, sas.Search (n));
	}
}

Answer 2

你把 Search（）方法中用到A[mid]的地方都改成A.[mid-1];
你原来那样会造成数组越界。
public int Search(int x)
{
int low=0;
int high=A.length;
while(low<=high){
int mid = (low+high)/2;
if(x>A[mid-1]){
low=mid+1;
}
else if(x<A[mid-1]){
high=mid-1;
}
else if(x==A[mid-1]){
return mid;
}
}
return 0;
}

追问

谢谢~~我还想问一下 为什么改为mid-1就可以了 我没有明白这一块的意思

追答

因为数组的下标是从0开始的，A[0]代表数组的第一个元素，A[1] 代表第二个...。你用mid返回的是该元素在数组中的位置，所以在用 A[mid]取对应元素的时候要将mid-1

Answer 3

24Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5
at SortAndSearch.Search(SortAndSearch.java:34)
at SortAndSearch.main(SortAndSearch.java:53)
int mid = (low+high)/2;
if(x>A[mid]){
low=mid+1;
}你的数组长度是5,可是mid最大只能=4，也就是数组越界

追问

谢谢你~~~我还想问一下为什么我的数组越界了，我没有明白这一块 为什么 改为mid-1 就可以了呢

追答

int mid = (low+high)/2;
出现了一种情况low=high=5，所以mid也等于5了