def search_rotated_array(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return target
if arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
arr = [4, 5, 6, 7, 0, 1, 2]
target = 1
print(search_rotated_array(arr, target))
def find_first_last_occurrence(arr, target):
def find_first():
left, right = 0, len(arr) - 1
index = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
index = mid
right = mid - 1
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return index
def find_last():
left, right = 0, len(arr) - 1
index = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
index = mid
left = mid + 1
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return index
first = find_first()
last = find_last()
if first == -1 or last == -1:
return -1
return (first, last)
arr = [1, 2, 2, 2, 3, 4, 5]
target = 2
print(find_first_last_occurrence(arr, target))
def find_smallest_greater_or_equal(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] >= target:
result = arr[mid]
right = mid - 1
else:
left = mid + 1
return result
arr = [1, 3, 5, 7, 9, 11]
target = 8
print(find_smallest_greater_or_equal(arr, target))