-3

我的算法应该告诉我“x”（值为 5）是否在排序数组中。但是，我一直得到 0。好吧，因为我的条件表明如果“x”不在数组中，则显示 0。我哪里出错了？

import java.util.Arrays;

public class binarySeacg {

public static void main (String[]args)
{
    int[] array = {10,7,11,5,13,8};
    exchangesort(array);
    binsearch(array,5);
    System.out.println(Arrays.toString(array));

}

public static void exchangesort(int[] S)
{
    int i,j,temp;

    for(i=0;i<S.length;i++)
        for(j=i+1;j<S.length;j++)
            if(S[i]>S[j])
            {
                temp = S[i];
                S[i] = S[j];
                S[j] = temp;
            }
}

public static int binsearch(int[] S, int x)
{
    int location, low, high, mid;

    low = 1; high = S.length;
    location = 0;

    while(low<=high && location==0)
    {
        mid =(low + high)/2;
        if(x== S[mid])
            location = mid;
        else if(x < S[mid])
            high = mid -1;
        else
            low = mid + 1;
    }
    System.out.println(location);
    return location;
}
}
4

4 回答 4

2

您设置low = 1;, 并且 5 是最小元素 - 所以它在索引 0 中 - 所以在 [1,S.length] 的子列表中 - 它确实不存在。

您应该设置low = 0;, 并从第一个元素开始 - 而不是第二个元素。（请记住，Java 中的索引从 0 开始，而不是 1）。

（PS，请注意，在这种特定情况下 - 算法是正确的，因为在排序列表中 - 5 在索引 0 中）。

于 2012-12-27T12:02:55.627 回答
1

因为，您正在尝试找到x您正在传递3并在您的列表中的价值。它不存在。因此，将其更改为其他值5，然后尝试。

此外，您应该开始low=0而不是low=1. 因为，它会一直错过第一个元素。

public static int binsearch(int[] S, int x)
{
    int location, low, high, mid;

    low = 0; high = S.length;
    location = 0;

    while(low<=high && location==0)
    {
        mid =(low + high)/2;
        if(x == S[mid])
        {
            location = mid;break;
        } 
        else if (x < S[mid])
        {
            high = mid - 1;
        } else
        {
            low = mid + 1;
        }
    }
    System.out.println(location);
    return location;
}

注意： 对于不同的输出，在binsearch(array,5);这里更改值，这是从main()方法调用的。请记住，更改列表中存在的值。

于 2012-12-27T12:03:03.220 回答
1

在这里，您正在对数组进行排序，然后将排序后的数组用于搜索元素。

如果搜索成功，则执行以下任务

位置=中；这意味着您将匹配元素的索引分配给 location 变量。

在这种情况下，元素 5 位于第 0 个索引中。

因此，您的 STDOUT 始终为 0

于 2012-12-27T12:30:03.280 回答
0
  1. 在 java 和大多数语言中，索引从 0 开始，而不是 1，并以 n-1 结束，而不是 n
  2. 对于二分查找，请仔细检查何时退出 while 循环，并始终记住您的 low 和 high 变量的含义，无论是 [low, high] 还是 [low, high)
  3. 对于这个特定问题，您还应该考虑如果数组中有 r 个重复项怎么办。是否返回数组中的第一个元素或任何元素
于 2012-12-29T05:06:57.603 回答