One of the cornerstones of the software engineering role is your understanding of and competency in using . data structures and algorithms During , recruiters and hiring managers will ask you to complete several coding questions to evaluate your knowledge of various data structures and algorithms. software engineering interviews One of the most fundamental algorithms software engineers should be experts in is a binary search. What Is Binary Search? Binary search is a versatile search algorithm that allows you to find an element within a sorted list. The key is to take advantage of sorted data to divide the search space in half at every step. Often, you can speed up naive algorithms from O(n) to O(log n), which is a considerable improvement. The binary search implementation we'll review below might differ slightly from what's readily found online. Still, we think it's easier to remember and less prone to off-by-one errors. Remember, however, that memorizing won't serve you when prepping for technical interviews. On the other hand, if you understand why binary search works, you'll be able to write good code that applies to various problems. Let's take a look at a simple example in . Python If you’re interested in seeing some examples of Binary Search in Java, check out . this Hackernoon article here Example #1 Imagine an interviewer gives you an array of s and s. They guaranteed that all the s would appear before all s. 0 1 0 1 So, arrays like , , and are valid, while are not. [0, 0, 1, 1, 1] [1, 1, 1] [0, 0, 0, 0] [1, 0], [0, 1, 0, 1] They ask you to find the first index of the array that is a . If no elements in the array are , then return . 1 1 -1 In Python, the signature for this function looks like this: def find_first_one(array: List[int]) -> int:
	pass A naive solution for this problem would look like this: def find_first_one(array: List[int]) -> int:
	for i in range(len(array)):
		if array[i] == 1:
			return i
	return -1 The worst case runtime of the naive algorithm is O(n) since, in the worst case, we'll have n-1 0s and one 1, and we'll need to scan the entire array. Optimizing With Binary Search Nevertheless, we can speed this up with a binary search. : Take a moment to review or properties of a given loop that are true before and after each loop iteration.* Tip "loop invariants," We start with two-pointers, called and , which represents the lowest and highest number that a possible answer could be. Since the answer is always an index, we can initially set and . lo hi lo = 0 hi = len(array)-1 For this problem, we'll let the loop invariant be and . array[lo] = 0 array[hi] = 1 This may not be the case initially, but we explicitly check those cases first. For example, if , the answer is just since is the first index where appears. If then the answer is since there are no s in the array. array[0] = 1 0 0 1 array[n-1] == 0 -1 1 In each iteration of binary search, we'll try to halve our search space. We take the midpoint between and (which can be computed as , and depending on whether the value of the array at that index is or , we can update either or to the midpoint. lo hi (lo+hi)/2) 0 1 lo hi def find_first_one(array: List[int]) -> int:
	n = len(array)
	if array[0] == 1:
		return 1 # first element is 1
	if array[n-1] == 0:
		return -1 # no 1s in this array
	lo = 0
	hi = n-1
	while lo + 1 < hi: # loop invariant: array[lo] = 0, array[hi] = 1
		mid = (lo + hi) // 2
		if array[mid] == 0:
			lo = mid
		else:
			hi = mid
	return hi it's easy to see why we set when ; that is, we want to ensure that that loop invariant is true. lo = mid array[mid] == 0 Now for our stopping condition. Notice . We did this because when , and are adjacent indices in the array. Once we have that, we immediately see that is the first index that is a because it has a immediately before it. lo+1 < hi lo+1 = hi lo hi hi 1 0 Another way to think of this is to find the place where the array switches from to (in contrast to finding the first ). 0 1 1 To compute the time complexity, we can note that we halve the distance between and at each iteration, which is O(log n). lo hi Other Applications for Binary Search Binary search can also be applied if there is only one point in time where a condition switches from false to true (or vice versa). In the example above, the condition is "array is equal to one." In other problems, this condition can be different, but the binary search can be applied if the underlying array has some structure where some prefix is all False, and the suffix is all True (or vice versa). Let's try it out with a few more examples. Example #2 Given a sorted array, find the index of the first element ≥ X (return -1 if no element ≥ X). def lower_bound(array: List[int], X: int) -> int:
	pass : consider loop invariants and Hint array[lo] < X array[hi] >= X Here's what a full solution could look like: def lower_bound(array: List[int], X: int) -> int:
	n = len(array)
	if array[n-1] < X:
		return -1
	if array[0] >= X:
		return 0
	lo = 0
	hi = n-1
	while lo+1 < hi: # array[lo] < X and array[hi] >= X.
		mid = (lo + hi) / 2
		if array[mid] < X:
			lo = mid
		else:
			hi = mid
	return hi Note that this code is similar to from Example #1 except for the different boundary checks. find_first_one The time complexity of this solution is . O(\log_2(n)) Example #3 Binary search works on data structures beyond arrays. To demonstrate, let's compute the square root of a non-negative number (to a certain level of precision.) We'll use loop invariants similarly to what we did above. PRECISION = 1e-6
def square_root(X: float) -> float:
	lo = 0
	hi = X
	while (hi - lo) > PRECISION: # lo^2 < X, hi^2 >= X
		mid = (lo + hi) / 2
		if mid*mid < X:
			lo = mid
		else:
			hi = mid
	return (lo + hi) / 2 Here, we've changed the termination condition to take into account precision. We also know the answer will be between lo and hi, so in the end, we can approximate it as . (lo+hi)/2 The runtime of this is . O(log (X / PRECISION)) And that's that! A binary search algorithm is a must-know for software engineering candidates. Therefore, it's best to count on these coding questions during your interviews. Of course, it's possible to find elements within sorted arrays using naive algorithms, but that's not necessarily going to impress a hiring manager. But you know what will? Efficiency and optimization are the names of the game for binary search. Nevertheless, there will be plenty of other that you'll be tested on during a software engineer interview. To learn more, check out the ." data structures and algorithms Exponent Software Engineering Course Also published . here

How to Use Binary Search in Your Software Engineering Interviews

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

A Hacker's Guide to Competitive Programming

A Beginner's Guide to Data Structures and Algorithms

A Guide to Examining & Modifying Executable Code

Binary Search In Detail

Binary Search In Java: Examples And Interview Tips

A Hacker's Guide to Competitive Programming

A Beginner's Guide to Data Structures and Algorithms

A Guide to Examining & Modifying Executable Code

Binary Search In Detail

Binary Search In Java: Examples And Interview Tips

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps