0

I am trying to implement a binary search in Java, but I am having some issues with my code. It works if the element I am looking for exists in the array. If it doesn't, the program doesn't print an error message. What I mean here is -

When I run my code - this is the output - 

Please enter array size
2
Please enter element 0
3
Please enter element 1
4
Sorted array elements[3, 4]


Please enter the element you want to find in the array
3
Match 3 found at index 0

If however, I look for an element that doesn't exist in the array, the program doesn't enter the else loop, and print an error message - It instead does this - 

Please enter array size
2
Please enter element 0
3
Please enter element 1
4
Sorted array elements[3, 4]


Please enter the element you want to find in the array
2
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
    at arraysPract.BinarySearch.findElement(BinarySearch.java:82)
    at arraysPract.BinarySearch.main(BinarySearch.java:54)

Here is the code - 

package arrays;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BinarySearch {
    static int[] binaryArr = null;

    public static void main(String[] args) {
        BufferedReader br = null;
        String size = "";

        try {
            System.out.println("Please enter array size");
            br = new BufferedReader(new InputStreamReader(System.in));
            size = br.readLine();
            if (size == null) {
                System.out.println("Size can't be null");
                return;
            }
            int ipSize = Integer.parseInt(size);
            binaryArr = new int[ipSize];
            String entry = "";
            for (int i = 0; i < ipSize; i++) {
                System.out.println("Please enter element " + i);
                entry = br.readLine();
                if (entry == null) {
                    System.out.println("Value can't be null");
                    return;
                }
                int arrEntry = Integer.parseInt(entry);
                binaryArr[i] = arrEntry;
            }

            Arrays.sort(binaryArr);
            System.out.println("Sorted array elements"  + Arrays.toString(binaryArr));
            System.out.println("\n");

            System.out.println("Please enter the element you want to find in the array");
            String findArrayElement = br.readLine();
            int find = Integer.parseInt(findArrayElement);      
            boolean elementExists = Arrays.asList(binaryArr).contains(find);            
            if (elementExists==false) {             
                findElement(binaryArr, find);
            }

            else {
                System.out.println("Element does not exist. Please try again");
            }

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static int findElement(int[] test, int keyElement) {
        boolean flag = true;
        int i = 0;
        for (i = test.length / 2; i >= 0 && i < test.length;) {
            if (keyElement == test[i]) {
                flag = false;
                break;
            } else if (keyElement > test[i]) {
                i++;
                if (keyElement == test[i]) {
                    flag = false;
                } else {
                    flag = true;
                }
            } else if (keyElement < test[i]) {
                i--;
                if (keyElement == test[i]) {
                    flag = false;
                } else {
                    flag = true;
                }
            }
        }

        if (flag == false) {
            System.out.println("Match " + keyElement + " found at index " + i);
        }
        return i;
    }
}

Request someone to please guide me if I am overlooking something thats an obvious error?

Also, there are several possible duplicates for this post - Binary search in java, Binary search in java etc. I just need help with reviewing my code, not in implementing the program :)

4

3 回答 3

0

这不是二分搜索，您应该继续将索引除以二（或递归，在递归版本中）。相反，您正在对数组的两半进行复杂的线性搜索（线性搜索，因为索引在每一步中递增/递减 1，一个常数）。

无论如何，您对 2 的问题是它小于数组的最小元素，因此i会递减直到达到 0（第一个元素）；此时，执行此行：

i--;

然后，test[i]被要求进行比较。但i将是-1，超出范围。测试后打电话i--，而不是之前。

请扔掉你的代码，仔细阅读这个很好的参考并正确实现二进制搜索：如果你了解二进制搜索的工作原理，代码会非常简单。

编辑：在这里查看线性搜索。

于 2013-05-07T23:24:38.937 回答
0

让我试着弄清楚二叉树是什么，希望它能让你的代码更容易一些。

二分搜索可以被认为是散布在树中的一堆变量。例如，如果树的根或树顶的数字为 8，则落在左侧的所有内容都小于或等于 8，而分支到该节点右侧的所有内容都更大。

于 2013-05-07T23:34:40.493 回答
0

无论您是否使用正确的算法，您的代码抛出 ArrayOutOfBoundsException 的原因是在递增或递减 i 将标志设置为 false 的情况下继续递增或递减 i。如果进入循环迭代找到匹配项，则跳出循环；在其他两种情况下，您增加/减少循环，然后再次检查，但如果标志被更改，您不会中断。在这种情况下，最好使用 while 或 do/while 循环。如果您在递增或递减之后删除第二个检查，您将实现您想要做的事情。

就算法而言，您不会增加数组索引，而是每次通过数组将搜索范围减半。

有用的一点是异常和堆栈跟踪告诉您出了什么问题（数组索引为-1）以及它发生的位置、方法和行（在 ArraysPract.BinarySearch.findElement(BinarySearch.java:82)

于 2013-05-07T23:48:40.647 回答