Sorted list of strings? Find length of list without using length function

Given a sorted list of strings and the last entry is null. You cannot use the list.length to determine the length o开发者_如何学Pythonf the list, but come with an approach efficient than O(n) to find the end Index of list or length of list?

Fast and dirty, but it should get things done.

This is just like a guess a number scenario. Start with an arbitrarily large number.

1. While key exists, double. Once IndexOutOfBounds is thrown, continue to step two.
2. Does that index exist?
   • Yes, then halve the difference between the next know number above the current index and add to the current index.
   • No? Then halve the difference between the next know number below the current index and the current one.

The good news? This is O(logn). The bad news? You have a potential of having logn/2 exceptions.

Sounds like homework.

Look at List.iterator() and the Iterator interface.

Using a binary search will give you O(logn)

So just search for the null entry :)

Easy: Use the 'List.size()' method. The Java 'List' interface does not have a "length" field or property.

;->