java - How to quickly insert an element into array with duplicates after all of the equal elements? -

i have arraylist, contains game objects sorted 'z' (float) position lower higher. i'm not sure if arraylist best choice have come such solution find index of insertion in complexity faster linear (worst case):

        gameobject go = new gameobject();         int index = 0;         int start = 0, end = displaylist.size(); // displaylist arraylist         while(end - start > 0)         {             index = (start + end) / 2;             if(go.depthz >= displaylist.get(index).depthz)                 start = index + 1;             else if(go.depthz < displaylist.get(index).depthz)                 end = index - 1;         }         while(index > 0 && go.depthz < displaylist.get(index).depthz)             index--;         while(index < displaylist.size() && go.depthz >= displaylist.get(index).depthz)             index++; 

the catch element has inserted in specific place in chain of elements equal value of depthz - @ end of chain. that's why need 2 additional while loops after binary search assume aren't expensive becouse binary search gives me approximation of place.

still i'm wondering if there's better solution or known algorithms such problem haven't heard of? maybe using different data structure arraylist? @ moment ignore worst case insertion o(n) (inserting @ begining or middle) becouse using normal list wouldn't able find index insert using method above.

you should try use balanced search tree (red-black tree example) instead of array. first can try use treemap witch uses red-black tree inside see if it's satisfy requirements. possible implementation:

map<float, list<object>> map = new treemap<float, list<object>>(){     @override     public list<object> get(object key) {         list<object> list = super.get(key);         if (list == null) {             list = new arraylist<object>();             put((float) key, list);         }         return list;     } }; 

example of usage:

map.get(0.5f).add("hello"); map.get(0.5f).add("world"); map.get(0.6f).add("!"); system.out.println(map);