mediumBinary SearchPattern: Binary Search
Find Element in Sorted Array Solution
Problem Statement
Given a sorted array of distinct integers `arr` and an integer `target`, return the index of the `target` if it is in the array, or -1 if it is not. You must write an algorithm with O(log n) runtime complexity.
Examples
Example 1:
Input:{"arr":"[2, 5, 7, 8, 11, 12]","target":13}
Output:-1
Explanation: The target 13 is not present in the array [2, 5, 7, 8, 11, 12], so we return -1.
Example 2:
Input:{"arr":"[-1, 0, 3, 5, 9, 12]","target":9}
Output:4
Explanation: The target 9 is found at index 4 in the array [-1, 0, 3, 5, 9, 12].
Example 3:
Input:{"arr":"[5]","target":5}
Output:0
Explanation: The target 5 is found at index 0 in the array [5].
Example 4:
Input:{"arr":"[2, 5, 7, 8, 11, 12]","target":13}
Output:The target is not present in the array.
Explanation: The target 13 is not present in the array [2, 5, 7, 8, 11, 12], returning -1.
Example 5:
Input:{"arr":"[-1, 0, 3, 5, 9, 12]","target":9}
Output:4
Explanation: The target 9 is found at index 4 in the array [-1, 0, 3, 5, 9, 12].
Example 6:
Input:{"arr":"[5]","target":5}
Output:0
Explanation: The target 5 is found at index 0 in the array [5].
Example 7:
Input:{"arr":[],"target":5}
Output:Array is empty.
Explanation: The array is empty, so no element exists.
Example 8:
Input:{"arr":"[1]","target":1}
Output:0
Explanation: The target 1 is found at index 0 in the array [1].
Example 9:
Input:{"arr":"[1]","target":0}
Output:-1
Explanation: The target 0 is not present in the array [1].
Constraints
- 1 <= arr.length <= 5 * 10^4
- -10^4 <= arr[i], target <= 10^4
- All the integers in arr are unique.
- arr is sorted in ascending order.
Time: O(log n) Space: O(1)
Utilize the binary search algorithm. Maintain a search space defined by `left` and `right` pointers. In each step, calculate the middle index `mid`, compare `arr[mid]` with `target`, and adjust the search space by moving `left` or `right` pointer. Repeat until the target is found or the search space is empty.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def search(arr: list[int], target: int) -> int:
if not arr:
return -1
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1