Leetcode 704 - Binary Search
Grow Your Tech Career. Meet Expert coaches from top companies
Understanding the problem
LeetCode 704 - Binary Search is a problem where you are given a sorted array of integers and a target value, and you need to find the target value in the array using binary search. Here is an example:
Input: nums = [-1,0,3,5,9,12] target = 9
Output: 4
Plan your solution
To solve this problem, we can use the binary search algorithm. Binary search is an efficient search algorithm that works by dividing the array in half at each step, and comparing the target value to the value at the middle index. If the target value is less than the value at the middle index, we search the left half of the array. If the target value is greater than the value at the middle index, we search the right half of the array. We continue this process until we find the target value, or until we determine that it is not present in the array.
Implement your solution
Here is the implementation of the search
function:
class Solution:
def search(self, nums: List[int], target: int) -> int:
# Set the start and end indices for the search
start = 0
end = len(nums) - 1
# Loop until the start and end indices meet or cross
while start <= end:
# Calculate the middle index
mid = (start + end) // 2
# If the target value is less than the value at the middle index, search the left half of the array
if target < nums[mid]:
end = mid - 1
# If the target value is greater than the value at the middle index, search the right half of the array
elif target > nums[mid]:
start = mid + 1
# If the target value is equal to the value at the middle index, return the middle index
else:
return mid
# If the target value is not found, return -1
return -1
Test your solution
# Test case 1
nums = [-1,0,3,5,9,12]
target = 9
expected_output = 4
assert Solution().search(nums, target) == expected_output
# Test case 2
nums = [-1,0,3,5,9,12]
target = 12
expected_output = 5
assert Solution().search(nums, target) == expected_output
# Test case 3
nums = [-1,0,3,5,9,12]
target = -1
expected_output = 0
assert Solution().search(nums, target) == expected_output
# Test case 4
nums = [-1,0,3,5,9,12]
target = 4
expected_output = -1
assert Solution().search(nums, target) == expected_output
# Test case 5
nums = [-1,0,3,5,9,12]
target = 6
expected_output = -1
assert Solution().search(nums, target) == expected_output
Grow Your Tech Career. Meet Expert coaches from top companies
Related: