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
 Initialize Pointers: Start with two pointers,
left
andright
, representing the current search range.left
starts at the beginning of the array, andright
starts at the end.  Binary Search: Repeat the following steps until
left
is greater thanright
: a. Calculate Midpoint: Compute the midpoint betweenleft
andright
. 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.
 Return Not Found: If the loop ends without finding the target, return 1.
Code


Explanation
 The
while
loop continues as long as the search range is valid (left
is less than or equal toright
).  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)
 Define the interface Input: Array of integers, target value (integer) Output: index of the target location (integer)
 Array is sorted. Precondition
 No duplicates
 At least there will be one element
 Return 1 if not found?
 What is the invariant?
 Assume that the list is sorted
IMPLEMENTATION LEVEL COMES LATER
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.
 Base cases
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
 How many subproblems do we have?
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


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:
“Find the Duplicate Number” (LeetCode 287): This problem can help you understand the concept of searching in an array.
“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.
“Find Smallest Letter Greater Than Target” (LeetCode 744): This problem helps you learn about searching in a sorted array with specific conditions.
“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.
“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.
“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.
“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.
“Valid Perfect Square” (LeetCode 367): This problem involves finding a square root of a number which can be solved by using binary search.
“Pow(x, n)” (LeetCode 50): The concept of binary search can be used in this problem to speed up the calculation of power.
“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.


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:
 Input: An array of integers (
nums
) sorted in ascending order, and an integer (target
).  Output: An integer, the index of
target
in the arraynums
iftarget
exists innums
. Otherwise, 1.  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:
Understanding Variables: This includes knowing how to declare variables, assign values to them, and update their values.
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.
Conditionals: You need to understand
if
,elif
, andelse
statements to perform different actions based on different conditions.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.
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>=
.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.
Functions: Understanding how to define and call functions is necessary to implement a binary search.
Recursion (Optional): Binary search can also be implemented recursively, which involves a function calling itself with different parameters.
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 tryexcept blocks.
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
 Understanding Variables


 Arrays or Lists


 Conditionals


 Loops


 Comparison Operators


 Mathematical Operations


 Functions


 Recursion


 Error Handling


 Binary Search Algorithm


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: threewaycomparison twopointers reduceinputbyhalf
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


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.


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).