hardBinary SearchPattern: Binary Search
Index of Target Value Solution
Problem Statement
Implement a function to find the index of a target value in a sorted sequence of unique integers using binary search.
Examples
Example 1:
Input:[1, 2, 3, 4, 5]
Output:-1
Explanation: The function should return the index of the target value 4 in the sorted sequence [1, 2, 3, 4, 5].
Example 2:
Input:[10, 20, 30, 40, 50]
Output:-1
Explanation: The function should return -1 as the target value 25 is not present in the sorted sequence [10, 20, 30, 40, 50].
Example 3:
Input:[100, 200, 300, 400, 500]
Output:-1
Explanation: The function should return the index of the first element in the sorted sequence [100, 200, 300, 400, 500].
Constraints
- The input sequence is sorted in ascending order.
- The input sequence contains unique integers.
- The target value may or may not be present in the sequence.
Time: O(log n) Space: O(1)
The binary search algorithm is an efficient approach to find the target value in a sorted sequence, with a time complexity of O(log n).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def binary_search(sequence, target):
if not sequence:
return -1
left, right = 0, len(sequence) - 1
while left <= right:
mid = (left + right) // 2
if sequence[mid] == target:
return mid
elif sequence[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1