Leetcode 704 - Binary Search

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

Related:

• binary subarrays with sum
• search a 2d matrix ii
• search a 2d matrix
• search in rotated sorted array
• unique binary search trees

Related Posts

• Leetcode 424 - Longest Repeating Character Replacement
• Two Sum and Its Variants
• Leetcode 1004 - Max Consecutive Ones III
• Leetcode 222 - Count Complete Tree Nodes
• Leetcode 1027 - Longest Arithmetic Subsequence
• Question 1299 on leetcode
• Leetcode 240 - Search a 2D Matrix II
• Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
• Leetcode 239 - Sliding Window Maximum
• Leetcode 209 - Minimum Size Subarray Sum
• LeetCode 230 - Kth Smallest Element in a BST with Code
• advanced-applications-of-binary-search
• Leetcode 96 - Unique Binary Search Trees
• Leetcode 540 - Single Element in a Sorted Array
• Leetcode 1283 - Find the Smallest Divisor Given a Threshold
• Leetcode 74 - Search a 2D Matrix
• Leetcode 300 - Longest Increasing Subsequence
• Leetcode 930 - Binary Subarrays With Sum
• Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
• Leetcode 643 - Maximum Average Subarray I
• LeetCode - Two Sum Solution with Code
• a-binary-search-template
• Leetcode 1358 - Number of Substrings Containing All Three Characters
• Leetcode 33 - Search in Rotated Sorted Array
• Leetcode 1151 - Minimum Swaps to Group All 1’s Together