src.search_rot_sort_array

Classes

Solution()

class src.search_rot_sort_array.Solution[source][source]
search(nums: list[int], target: int) → int[source]

Thought process

  • The key thing to remember here is that all this is, is a modified binary search

  • All the modification nums[l] <= nums[m] does is ensure the condition required in binary search - that the target is in the interval of the split - continues to hold

  • Again we determine the midpoint as l + (r - l) // 2

  • The different operations on the two pointers (same as for regular binary search) simply adjust the pointers to their correct positions in the segments ; that is, the l points to the leftmost index of the segment and r points to the rightmost index of the segment

Notes

  • time complexity is \(O(log n)\)

  • space complexity is \(O(1)\)