Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1
Constraints:
1 <= nums.length <= 104-104 < nums[i], target < 104nums are unique.nums is sorted in ascending order.The iterative binary search approach involves using a loop to divide the array into halves repeatedly until the target is found or the search range is empty. This approach utilizes two pointers, 'low' and 'high', that represent the current search bounds.
This C code implements an iterative binary search. It uses a loop to adjust the low and high pointers based on comparisons, eventually finding the target or concluding it is not present.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n), as we divide the search space in half each time.
Space Complexity: O(1), only a constant amount of space is used.
The recursive binary search involves calling a function that repeatedly calls itself with updated bounds until the target is found or the bounds overlap. This approach provides a cleaner implementation at the cost of additional space used by the call stack.
This C solution uses recursion to split the problem into smaller subproblems, updating 'low' and 'high' in each recursive call.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n)
Space Complexity: O(log n) due to the stack space used by recursion.
| Approach | Complexity |
|---|---|
| Iterative Binary Search | Time Complexity: O(log n), as we divide the search space in half each time. |
| Recursive Binary Search | Time Complexity: O(log n) |
8 patterns to solve 80% Leetcode problems • Sahil & Sarra • 656,569 views views
Watch 9 more video solutions →Practice Binary Search with our built-in code editor and test cases.
Practice on FleetCode