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.