At every step, one half of the rotated array is still sorted. Detect it and decide whether the target lies there.