grid47 Exploring patterns and algorithms
Aug 28, 2024
6 min read
Solution to LeetCode 704: Binary Search Problem
You are given a sorted array of integers and a target value. Your task is to search for the target in the array. If the target exists, return its index. If it does not exist, return -1. You must achieve a time complexity of O(log n).
Problem
Approach
Steps
Complexity
Input: The input consists of a sorted array of integers and a target integer. The array is sorted in ascending order.
Example: nums = [1, 3, 5, 7, 9, 11], target = 5
Constraints:
• 1 <= nums.length <= 10^4
• -10^4 < nums[i], target < 10^4
• All integers in nums are unique.
• nums is sorted in ascending order.
Output: The function should return the index of the target if it exists in the array. If the target does not exist, return -1.
Example: Output: 2
Constraints:
• The result should be the index of the target value in the sorted array.
Goal: Implement an efficient search algorithm to find the target in the sorted array using binary search.
Steps:
• 1. Initialize two pointers: left and right, pointing to the first and last elements of the array.
• 2. Calculate the middle index as the average of left and right.
• 3. If the middle element is equal to the target, return the middle index.
• 4. If the middle element is less than the target, update the left pointer to mid + 1.
• 5. If the middle element is greater than the target, update the right pointer to mid - 1.
• 6. If the left pointer exceeds the right, return -1 indicating the target is not in the array.
Goal: The array is sorted in ascending order, and the target is an integer within the given range.
Steps:
• The array is guaranteed to be sorted in ascending order.
• All integers in the array are unique.
Assumptions:
• The target is a valid integer within the given range.
• The array is sorted and contains unique integers.
• Explanation: The target 8 does not exist in the array, so the function will return -1.
Approach: The optimal solution for this problem is binary search, which allows searching in O(log n) time complexity. We will iteratively narrow down the search range by updating the left and right pointers based on the comparison with the middle element.
Observations:
• Since the array is sorted, binary search is ideal for this problem to achieve O(log n) time complexity.
• We can solve this efficiently by halving the search space at each step.
Steps:
• Step 1: Initialize two pointers, left and right, to the start and end of the array.
• Step 2: Calculate the middle index and compare the middle element with the target.
• Step 3: If the middle element matches the target, return the index.
• Step 4: If the middle element is smaller than the target, move the left pointer to mid + 1.
• Step 5: If the middle element is larger than the target, move the right pointer to mid - 1.
• Step 6: If the left pointer exceeds the right pointer, return -1 indicating the target is not found.
Empty Inputs:
• The array is never empty in this problem, as the constraint guarantees that nums.length >= 1.
Large Inputs:
• For very large arrays, ensure that the binary search approach handles the input efficiently.
Special Values:
• The target could be the first or last element of the array.
Constraints:
• Ensure that the binary search efficiently narrows down the search space for large arrays.
intsearch(vector<int>& nums, int target) {
int l =0, r = nums.size() -1;
while(l <= r) {
int mid = l + (r - l) /2;
if(nums[mid] == target) return mid;
if(nums[mid] < target) l = mid +1;
else r = mid -1;
}
return-1;
}
1 : Function Definition
intsearch(vector<int>& nums, int target) {
Define a function 'search' that takes a vector of integers 'nums' and an integer 'target' to return the index of the target element, or -1 if not found.
2 : Variable Initialization
int l =0, r = nums.size() -1;
Initialize two variables, 'l' for the left pointer and 'r' for the right pointer, which represent the range of indices to search within the array.
3 : While Loop
while(l <= r) {
Start a while loop that will execute as long as the left pointer is less than or equal to the right pointer, meaning there is still a search range to explore.
4 : Midpoint Calculation
int mid = l + (r - l) /2;
Calculate the midpoint index 'mid' to divide the search space in half. Using 'l + (r - l) / 2' prevents potential overflow that could happen with large values of 'l' and 'r'.
5 : Target Comparison
if(nums[mid] == target) return mid;
If the element at the midpoint is equal to the target, return the index 'mid' where the target is located.
6 : Left Pointer Update
if(nums[mid] < target) l = mid +1;
If the value at the midpoint is less than the target, update the left pointer 'l' to 'mid + 1' to search the right half of the array.
7 : Right Pointer Update
else r = mid -1;
If the value at the midpoint is greater than the target, update the right pointer 'r' to 'mid - 1' to search the left half of the array.
8 : Return Not Found
return-1;
If the target element is not found within the array, return -1 indicating that the search was unsuccessful.
Best Case: O(1), if the target is found at the middle of the array.
Average Case: O(log n), for each search operation.
Worst Case: O(log n), in the case where the search space is halved at each step.
Description: The time complexity is logarithmic due to the binary search algorithm.
Best Case: O(1), as binary search does not require additional space.
Worst Case: O(1), as the space complexity is constant for binary search.
Description: The space complexity is constant since we only use a few pointers to track the search range.
