java - Java 中的二进制搜索 - 学习它 "my way"

Question

所以我正在尝试自学如何在 Java 中实现二分搜索，因为该主题可能已经泄露，但我遇到了一些麻烦。

看，我有点固执，我宁愿不只是从互联网上复制一些实现。

为了自学这个，我创建了一个非常(非常)粗糙的小类，如下所示:

public class bSearch{

/**
 * @param args
 */

public static void main(String[] args) {

    int one = 1;
    int two = 2;
    int three = 3;
    int four = 4;
    int five = 5;
    int six = 6;

    ArrayList tab = new ArrayList();

    tab.add(one);
    tab.add(two);
    tab.add(three);
    tab.add(four);
    tab.add(five);
    tab.add(six);

    System.out.println(bSearch(tab, 53));

}

@SuppressWarnings({ "rawtypes", "unchecked" })
public static int bSearch(ArrayList tab, int key) {

    if (tab.size() == 0)
        return 0;

    if ((int) tab.get(tab.size() / 2) == key)
        return key;

    ArrayList smallerThanKey = new ArrayList();
    ArrayList largerThanKey = new ArrayList();

    for (int i = 0; i < (tab.size() + 1) / 2; i++) {
        smallerThanKey.add(tab.get(i));
    }

    System.out.println("Smaller array = " + smallerThanKey);

    for (int i = (tab.size() + 1) / 2; i < tab.size(); i++) {
        largerThanKey.add(tab.get(i));
    }

    System.out.println("Larger array = " + largerThanKey);

    if (key < (int) tab.get(tab.size() / 2)) {
        bSearch(smallerThanKey, key);
    } else {
        bSearch(largerThanKey, key);
    }

    return key;
    }
}

如您所见，它远谈不上漂亮，但对于像我这样的新手来说已经足够清楚了，无论如何。

现在，问题来了；当我向它提供 ArrayList 中的数字时，它会将数字反馈给我(万岁!)，但是当我向它提供不在 ArrayList 中的数字时，它仍然会把我的号码反馈给我(嘘!)。

我感觉我的错误很小，但我就是看不出来。

还是我都错了，还有一些更大的根本性错误？

非常感谢您的帮助!

更新

感谢所有建设性的评论和回答!你们中的一些人在正确的方向上提供了许多有用的指导。 +1 给所有在正确的道路上碰到我的人。

按照您给出的建议，主要是关于我的递归没有正确结束，我添加了一些 return 语句，如下所示；

if (key < (int) tab.get(tab.size() / 2)) {
     return bSearch(smallerThanKey, key);
} else {
     return bSearch(largerThanKey, key);
}

现在，这样做离我想要实现的目标又近了一步。

如果找不到数字，我现在得到 0，如果找到了，则得到数字本身。。因此正在取得进展!

但是，如果我让它搜索负数或零，它就不起作用(我不知道为什么我应该这样做，但只是把它扔在那里)。

这个问题有解决办法吗，还是我问错了树？

Answer 1

编辑

就像您要问的确切问题的快速解决方案一样:您需要将最后几行更改为以下内容

  if (key < (int) tab.get(tab.size() / 2)) {
      return bSearch(smallerThanKey, key);
  } else {
      return bSearch(largerThanKey, key);
  }
}

话虽如此，让我再指出几个我在这里看到的问题:

(a) 您可以使用泛型。那就是使用 ArrayList<Integer>而不仅仅是 ArrayList这将使您免于所有这些强制转换。

(b) 与其返回您找到的值，不如返回值所在的 ArrayList 中的索引，如果未找到则返回 -1。原因如下:返回 key为调用者提供很少的新信息。我的意思是 - 调用者已经知道 key 是什么。如果您将索引返回给键，您会让调用者知道是否找到了该键，以及是否找到了它在列表中的位置。

(c) 每次进入 bSearch() 时，您基本上都复制了整个列表: 您将大约一半的列表复制到 smallerThanKey 中和(大约)一半到greaterThanKey .这意味着此实现的复杂性不是 O(log n)而是O(n) .

(编辑#2)

总结 (a)、(b)、(c) 点，下面是该方法的编写方式:

public static int bSearch(ArrayList<Integer> tab, int key) {
  return bSearch(tab, 0, tab.size(), key);
}

public static int bSearch(ArrayList<Integer> tab, int begin, int end, int key) {
    int size = end - begin;
    if (size <= 0)
        return -1;

    int midPoint = (begin + end) / 2;
    int midValue = tab.get(midPoint);
    if (midValue == key)
        return midPoint;

    if (key < midValue) {
        return bSearch(tab, begin, midPoint, key);
    } else {
        return bSearch(tab, midPoint + 1, end, key);
    }
}

如您所见，我添加了第二种方法，它接受 begin。 , end参数。这些参数让方法应该查看列表的哪一部分。这比创建一个新列表并将元素复制到它要便宜得多。相反，递归函数只使用列表对象并简单地用新的 begin 调用自身。 , end值(value)观。

返回值现在是 key 的索引在列表中(如果未找到，则为 -1)。