Since each of Alice's days can eliminate at most 2 caves, even if Bob never moves it still takes 9 days to know his location with certainty. We can take that as a lower limit. 

Now consider the following strategy. (Assume Bob is never found unless he must be):

First Pass

On day #1, Alice checks (1,3). Bob might be in [2,4] or else 5+, after he moves he's in [1,3] or 4+

On day #2, Alice checks (4,6). Bob might be in [1,3,5,7], or else in 8+. After he moves, he's in [2,4,6] or 7+

On day #3, Alice checks (7,9). Bob might be in [2,4,6,8,10] or else 11+. After he moves, he's in [1,3,5,7,9] or 10+

On day #4, Alice checks (10,12). Bob might be in [1,3,5,7,9,11,13] or else 14+. After he moves he's in [2,4,6,8,10,12] or 13+

On day #5, Alice checks (13,15). Bob might be in [2,4,6,8,10,12,14,16] or else 17. After he moves, he's in [1,3,5,7,9,11,13,15] or 16+.

On day #6, Alice checks (16,1). Bob is now guaranteed to be in an odd cave 3+. After he moves, he's in an even cave. 

Second Pass

On day #7, Alice checks (2,4) Bob is now in an even cave 6+, and after he moves he's in an odd cave 5+

On day #8, Alice checks (5,7) Bob is now in an odd cave 9+ and after he moves he's in an even cave 8+

On day #9, Alice checks (8,10) Bob is now in an even cave 12+, and after he moves he's in an odd cave 11+

On day #10, Alice checks (11,13) Bob is now in an odd cave 15+ and after he moves he's in an even cave 14+

On day #11, Alice checks (14,16) and finds Bob.

I haven't proved that 11 days is a minimum, but given the lower limit of 9 days there doesn't seem to be much wiggle room. Still, on day #6 we get no actual information from the 2nd guess. Even if Alice just guesses 16 twice, after Bob's move he's still in an even cave. Likewise, on day #11, Alice doesn't really need to check both caves, since after checking the first one she knows with certainty where Bob is located. It's at least possible that some other algorithm wouldn't "waste" these guesses and could result in only requiring 10 days.