For a random index m, compare nums[m] with its neighbor, one of the answer belongs to the interval that the bigger element belongs to too, and we can optimize our program based on this.

Another code.