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.

;->