%%python
def search_rotated_array(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
print(search_rotated_array(nums, target))
4
%%python
def find_first_and_last(nums, target):
def find_bound(is_first):
left, right = 0, len(nums) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
result = mid
if is_first:
right = mid - 1
else:
left = mid + 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
first = find_bound(True)
last = find_bound(False)
return [first, last]
nums = [5, 7, 7, 8, 8, 10]
target = 8
print(find_first_and_last(nums, target))
[3, 4]
%%python
def find_ceiling(nums, target):
left, right = 0, len(nums) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] >= target:
result = nums[mid]
right = mid - 1
else:
left = mid + 1
return result
nums = [1, 3, 5, 7, 9]
target = 6
print(find_ceiling(nums, target))
7