Binary search problems
Typical problems include rotate array. I am not familiar with this kind of problem, especially how to divide them into different situation.
Usually, the end situation written as start < end
, so that the final return value can be written as nums[start] to avoid some edge situation. In addition, the mid value calculation should be written as mid = start + (end - start)/2
to avoid overflow of number range.
153. Find Minimum in Rotated Sorted Array
Divide the situation into array rotated & not rotated. If nums[start] < nums[end]
, the array is not rotated, simply return nums[0]. Then for the rotated situation, there are 2 cases:
nums[mid] < nums[end] && nums[mid] < nums[start]
, minimum is on left side.nums[mid] > nums[end] && nums[mid] > nums[start]
, minimum is on right side.
Can write end side check condition, (if use start will have decreasing order edge case.)notice that when change value of start & end need to deal with edge case.(when carry with no equal, update, otherwise, keep)
33.Search in rotated array
Same as previous problem, use nums[mid] & nums[right] to judge which part is ordered, then judge target lies in which part to get the result.
287. Find the Duplicate Number
Use idea same as linkedlist cycle 2. Very tricky to understand array entry since they are all in 1-N range. Just find the entry of the cycle.
Review of find minimum in sorted array
Always compare the nums[mid] with nums[end]; When you classify different situations, you need also to consider when the rotated array already become a sorted array, you need to combine this situation into several another situation, this is important. Otherwise, answers error when you don’t consider the array shrink process.