Binary Search

TODO: Write the binary search algorithm recursively

Your task is to implement a function to search for a target value in a sorted array. Since the array is sorted, you can apply binary search to achieve (O(\log n)) runtime complexity.

Algorithm

  1. Initialize Pointers: Start with two pointers, left and right, representing the current search range. left starts at the beginning of the array, and right starts at the end.
  2. Binary Search: Repeat the following steps until left is greater than right: a. Calculate Midpoint: Compute the midpoint between left and right. b. Check Mid Value: Compare the value at the midpoint with the target.
    • If it’s equal to the target, return the index of the midpoint.
    • If it’s less than the target, update left to the midpoint plus one.
    • If it’s greater than the target, update right to the midpoint minus one.
  3. Return Not Found: If the loop ends without finding the target, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

Explanation

  • The while loop continues as long as the search range is valid (left is less than or equal to right).
  • Within the loop, we check the midpoint’s value to decide how to update our search range.
  • If the target value isn’t found, we return -1.

Insights

  • Time Complexity: (O(\log n)), where (n) is the length of nums. The search range is halved at each step.
  • Space Complexity: (O(1)), as we only use a constant amount of extra space.

This code implements a standard binary search algorithm, tailored to the specific constraints of the problem, to efficiently find the target value’s index in the sorted array.

ANALYZE THE PROBELM (DON’T SOLVE IT)

  1. Define the interface Input: Array of integers, target value (integer) Output: index of the target location (integer)
  2. Array is sorted. Precondition
  3. No duplicates
  4. At least there will be one element
  5. Return -1 if not found?
  6. What is the invariant?
    • Assume that the list is sorted

IMPLEMENTATION LEVEL COMES LATER

  1. Recursive Approach

    • Base cases
      • What is the smallest instance of the problem?
      • One element array, return the element if it is the same, otherwise -1
      • If we use two pointers, if the low goes over the high We can terminate the recursion
      • Invariant: Low and high cannot cross each other.

  2. Reduce the search space by half Problem Decomposition

    • How many subproblems do we have?
      • log n will the number of total subproblems.
    • How many recursive calls do we need to make in the code?
      • Two recursive calls
      • Mid level, how you are going to either look at the right or left

  3. What is the unit of work?

    • Calculate the mid value

    • Check if the mid value is the target

    • Does this go before the recursive call or after the recursive call?

    • Before the recursive call

      • mid value mid = (start + end)/2

      If the mid value is the target we can return the index.

    • Returning boolean/string/array/integer from recursive function

      • Functional Recursion
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer}

def wrapper(nums, low, high, target)
    if high < low
        return -1
    end

    mid = (low+high)/2

    if target == nums[mid]
        return mid
    elsif target < nums[mid]
        wrapper(nums, low, mid-1, target)
    else
        wrapper(nums, mid+1, high, target)
    end
end

def search(nums, target)
    wrapper(nums, 0, nums.size-1, target)
end

Before tackling the Binary Search problem, familiarize yourself with the basics of arrays and recursion. Here are some simpler problems to understand the necessary concepts:

  1. “Find the Duplicate Number” (LeetCode 287): This problem can help you understand the concept of searching in an array.

  2. “Search Insert Position” (LeetCode 35): This problem involves finding a target value in a sorted array or determining where it would be if it were inserted in order.

  3. “Find Smallest Letter Greater Than Target” (LeetCode 744): This problem helps you learn about searching in a sorted array with specific conditions.

  4. “First Bad Version” (LeetCode 278): In this problem, you use binary search to minimize the number of checks you make to find the ‘first bad version’. It’s a good practical application of binary search.

  5. “Guess Number Higher or Lower” (LeetCode 374): This problem has a similar concept as binary search. It can help you understand the iterative process in binary search.

  6. “Two Sum II - Input array is sorted” (LeetCode 167): This problem can familiarize you with the concept of using two pointers in a sorted array, which is somewhat related to binary search.

  7. “Find Peak Element” (LeetCode 162): This problem can be solved by using binary search, and it’s a good problem to understand how binary search works on different conditions.

  8. “Valid Perfect Square” (LeetCode 367): This problem involves finding a square root of a number which can be solved by using binary search.

  9. “Pow(x, n)” (LeetCode 50): The concept of binary search can be used in this problem to speed up the calculation of power.

  10. “Sqrt(x)” (LeetCode 69): This problem also involves finding a square root of a number using binary search.

These cover binary search and how it can be applied in different scenarios.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums)
        while low < high:
            mid = (low + high) // 2
            if target > nums[mid]:
                low = mid + 1
            else:
                high = mid
        return low

Problem Classification

The task involves implementing a search function for a sorted array, which is a typical problem in Algorithms. More specifically, the problem requires the use of Binary Search, a fundamental algorithmic technique.

‘What’ Components:

  1. Input: An array of integers (nums) sorted in ascending order, and an integer (target).
  2. Output: An integer, the index of target in the array nums if target exists in nums. Otherwise, -1.
  3. Constraints: The algorithm should have a runtime complexity of O(log n), which suggests that a binary search approach should be employed.

This is a Search Problem, specifically, a Binary Search Problem. The task is to search for a particular item (target) in a given sorted list (nums). The characteristic of binary search is that it reduces the search space by half after every comparison, which leads to a logarithmic time complexity, hence the O(log n) requirement.

This problem is a standard binary search problem and is a great example to understand how log time complexity can be achieved in a sorted array. It highlights the importance of understanding the properties of data structures and how to utilize them effectively to solve problems.

Language Agnostic Coding Drills

Binary Search Algorithm can be broken down into the following units of learning:

  1. Understanding Variables: This includes knowing how to declare variables, assign values to them, and update their values.

  2. Arrays or Lists: Binary search operates on a sorted array or list, so understanding how to create and use arrays or lists is crucial. This includes understanding indexing and slicing.

  3. Conditionals: You need to understand if, elif, and else statements to perform different actions based on different conditions.

  4. Loops: A binary search uses a while loop to repeatedly divide the search space in half until the target value is found or until the search space is empty.

  5. Comparison Operators: In a binary search, you have to compare the target value with the middle element of the search space. You need to understand how to use comparison operators like ==, <, >, <=, and >=.

  6. Mathematical Operations: You’ll need to perform simple mathematical operations like addition, subtraction, multiplication, and division. In the context of a binary search, these are used to calculate the middle index of the search space.

  7. Functions: Understanding how to define and call functions is necessary to implement a binary search.

  8. Recursion (Optional): Binary search can also be implemented recursively, which involves a function calling itself with different parameters.

  9. Error Handling (Optional): You might want to handle errors like what happens when the target value is not in the array. This can be done using try-except blocks.

  10. Complete Binary Search Algorithm: Once you understand all the above components, you can combine them to write a complete binary search algorithm.

Solution for Coding Drills in Python

  1. Understanding Variables
1
2
3
4
5

# Declaring a variable
a = 5

# Updating a variable
a = 10
  1. Arrays or Lists
1
2
3
4
5
6
7
8

# Creating a list
my_list = [1, 2, 3, 4, 5]

# Indexing a list
print(my_list[0])  # Outputs: 1

# Slicing a list
print(my_list[1:3])  # Outputs: [2, 3]
  1. Conditionals
1
2
3
4
5
6
7
8

a = 5
b = 10
if a < b:
    print("a is less than b")
elif a > b:
    print("a is greater than b")
else:
    print("a is equal to b")
  1. Loops
1
2
3
4
5

# A simple while loop
i = 0
while i < 5:
    print(i)
    i += 1
  1. Comparison Operators
1
2
3
4
5
6
7
8

a = 5
b = 10

print(a == b)  # False
print(a < b)  # True
print(a > b)  # False
print(a <= b)  # True
print(a >= b)  # False
  1. Mathematical Operations
1
2
3
4
5
6
7

a = 5
b = 10

print(a + b)  # 15
print(b - a)  # 5
print(a * b)  # 50
print(b / a)  # 2.0
  1. Functions
1
2
3
4
5

# A simple function that adds two numbers
def add(a, b):
    return a + b

print(add(5, 10))  # 15
  1. Recursion
1
2
3
4
5
6
7
8

# A function that computes factorial using recursion
def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))  # 120
  1. Error Handling
1
2
3
4

try:
    a = 5 / 0
except ZeroDivisionError:
    print("Cannot divide by zero")
  1. Binary Search Algorithm
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def binary_search(arr, low, high, x):
    if high >= low:
        mid = (high + low) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)
        else:
            return binary_search(arr, mid + 1, high, x)
    else:
        return -1

arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, 0, len(arr)-1, x)
print(result)  # 3

Coding Skill Exercise #16

Binary Search

Write a method that finds a given integer in an array using binary search.

Knowledge Gap Finder

If you are unable to code the solution, answer the following questions and reply to this email to get customized lesson.

Was the problem statement clear to you when you read it? What did you think of doing first? Were you reminded of a construct in general or a general structure of solution that you thought would be useful? Have you previously seen problems that resemble this one? Did you feel stuck at any point while working on this problem? What did you choose as your test case? Do you think you’ve covered all possible scenarios with your tests? What program design techniques did you apply to solve this problem? Are there any constructs of the programming language that you find difficult or confusing to use? What issues make programming constructs difficult to use? For example, the keyword used, the syntax, the examples, the documentation for the construct, etc.

Feel free to forward this email to your friends so they can subscribe here. https://codingskill.biz

excerpt: This covers the recursive and iterative implementation of binary search algorithm. tags: three-way-comparison two-pointers reduce-input-by-half

We keep track of the left and right indices denoting the section of the list that needs to be searched. How can we compute the index of the element that we compare to the key as a function of the left and right indices?

The algorithm keeps track of the largest and smallest indices where the target item might be located in the array. The initial values of those bounds are 0 and the largest index in the array.

The mid point of the array is calculated. If the target is less than the array’s value at mid, the search is carried out in the left half of the array. If the target is greater than the array’s value at mid, the search is carried out in the right half of the array. If the target is equal to the value at the mid index, the index mid is returned.

The diagram shows a binary search for the value 77.

Iterative Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def binary_search(array, target)
  low = 0
  high = array.size - 1
  
  while low <= high
    mid = (low + high) / 2
    
    if target == array[mid]
      return mid
    elsif target < array[mid]
      high = mid - 1
    else
      low = mid + 1
    end
  end
end

array = [16, 21, 22, 39, 41, 49, 52, 57, 60, 65, 71, 77, 90, 91]

p binary_search(array, 77)

Building Blocks

  • Three Way Comparison
  • Two Pointers

Recursive Implementation

The recursive algorithm makes two recursive calls to search in the appropriate half of the array for the target element.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def wrapper(array, target, low, high)
  mid = (low + high)/2
  
  if target == array[mid]
    return mid
  elsif target < array[mid]
    wrapper(array, target, low, mid - 1)
  else
    wrapper(array, target, mid + 1, high)
  end
end

def binary_search(array, target)
  low = 0
  high = array.size - 1
  
  wrapper(array, target, low, high)
end

array = [16, 21, 22, 39, 41, 49, 52, 57, 60, 65, 71, 77, 90, 91]

p binary_search(array, 77)

At each step, the search space is reduced by half. If the array contains N items, after O(log N) steps, the section of the array that might hold the target contains only one item, so we either find the item or conclude that it is not in the array. This means the runtime of Binary Search is O(log N).