Need Help With A Binary Search

Discussion in 'Spigot Plugin Development' started by VirusBrandon, May 13, 2016.

  1. Hi all,

    I've been starring at this for quite of time now.

    I have an ArrayList of Objects of size ~2000.

    What I want to do is recursively visit every index of
    that arraylist as fast as possible with as little system
    resources as possible.

    I want a solution that is far faster than just
    looping thru the list.

    A correct implementation of a Binary search
    on an ArrayList of this size, should be able to
    reach every index in less than 20 iterations.

    But I keep getting stackOverflow errors.

    Here's what I have:
    public void search(int low, int high, Cell cell, int i){
    if((high-low)>1){
    int middle = ((high - low)/2);
    search(low,middle,cell,(i+1));
    search((middle+1),high,cell,(i+1));
    } else {
    Bukkit.broadcastMessage("Itr: "+i);
    }
    }


    Anyone have any ideas? I hope I'm not way off :)
     
  2. If I were you, I'd consider using a HashSet instead of an ArrayList. An ArrayList has an O(n) search implementation but a HashSet has an O(1). Which means that regardless of the size of the HashSet, it will always find the item you're looking for in the same amount of time. However, the more items you have in an ArrayList, the longer it will take for you to find and item in it.

    Overall, if all the objects are unique, you won't have to code anything complex if you switch to using a HashSet. More info on the Big O annotation can be found here: https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
     
  3. What is the fastest method that you know of for search a relatively large set of data
    as quickly as possible without having any sort of target value to pass in?

    I just need an algorithm to visit all of the data points as fast as possible
    with using as little system resources as possible.

    The Hashset appears to require input for what data I'm looking for.
     
  4. I mean... you can't just search "something", you need to search for a particular item. I don't get the point of parsing everything without a target value
     
  5. I'm making a plugin where I move around a map where
    those ~2000 objects we visually represented on the map
    and I need to access those objects' locations to determine
    if I am close enough to any of the objects to collect it and
    get points.