Hello. In Google did not find almost any information about this.

Tell me, how long can you find an element by its value in Vector'e and ArrayList'e? What explains the search time? For some reason I think that O (n), because you still have to go over all the elements until you find the one you need. But, on the other hand, for some reason it seems to me that for O (log (n))

Thank you in advance

  • sorted for log (n) with binary search - pavel

1 answer 1

If the array is not sorted, then the complexity of the search algorithm is obviously O(N) , since we cannot draw conclusions about the values ​​of neighboring elements based on the value of the selected element.

In the case of a sorted array, you can use binary search , reducing the complexity to O(log(N)) .

With regards to the differences between the search in ArrayList and Vector - there is practically no difference, since each of these containers provides access to the element by index, which is crucial for binary search.