Find the word in this paragraph

Question

You are given a paragraph in which the length of all words in a line has the following properties:

• Odd position words are in increasing order of their length.
• Even-numbered position words are in decreasing order of their length.

You have been given a word, and you need to write a code to search for it in this section and return the line number.

Answer 1

If each line is given by a list of words, these are actually two sorted sublists:

(1) odd word list: sorted by length by length
(2) even-word list: sorted by length

Use binary search in both lists with a comparator: word.length()
As soon as you find a match [the word you are looking for and the word in the list that you are currently looking at) is the same length: check if it is the same word.

repeated for each row.

Complexity [for each line]: O(logn * |S|) where |S| is the size of your word, and n is the number of words per line.

Answer 2

There seems to be no requirement for the complexity of typing runtimes - so why not just implement a linear search? Perhaps this is weird / even just added to embarrass you! Keep it simple;)