Search in Rotated Sorted ArrayMediumAcceptance Rate 39.2%Search for a target in a rotated sorted array.ExamplesExample 1Inputnums = [4,5,6,7,0,1,2], target = 0Output4Constraints1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4-10^4 <= target <= 10^4