Binary search

Find a target value in a sorted array. Binary search works by eliminating half of the array that isn’t accurate to the target value. This repeats until the target value is the last element of the array.

How it works:

The process

Given an array, let’s say you want to find where the element 15 is in the array below:

my_array = [1, 3, 5, 7, 9, 15, 20]
target_value = 15

1. Find the middle value of the array. This is done by getting the length of the array, dividing it by two. If dividing it by 2 gives a decimal, you can round either up or down (just make sure it is consistent).

my_array = [1, 3, 5, 7, 9, 15, 20]
target_value = 15
length_of_array = len(my_array)
 
middle_value = length_of_array // 2 # // is floor division, rounds it down
middle_element = my_array[middle_value]

2. Compare the middle_element with your target value. If it is lower than your target_value, then you can safely eliminate all numbers less than that middle value (including itself). If it is higher, then you can safely eliminate all numbers greater than that middle value (including itself).

my_array = [1, 3, 5, 7, 9, 15, 20]
target_value = 15
length_of_array = len(my_array)
 
middle_index = length_of_array // 2
middle_element = my_array[middle_index]
 
if middle_element == target_value:
	print("target value is in array!")
	break
elif middle_element < target_value:
	new_array = my_array[middle_index+1:]
elif middle_element > target_value:
	new_array = my_array[:middle_value-1]
my_array = new_array

3. Repeat this process with the new array. It would look like so:

1st iteration:
[1, 3, 5, 7, 9, 15, 20]
middle index = 7/2 = 3.5, rounded to a 3
middle element = 7

7 < 15:
new array = [9, 15, 20]

2nd iteration:
[9, 15, 20]
middle index = 3/2 = 1.5, roudded to a 1
middle element = 15

15 = 15
print "Found target value!")

Code implementation

Now that you know how the algorithm works, here’s how to properly implement it.

1. Create 2 pointers, one for left and one for right. These acts as ‘pointers’ to the range of the list you need to check.

is_found = False
my_array = [1, 3, 5, 7, 9, 15, 20]
target_value = 15
 
left = 0
right = len(my_array) - 1 # 6

 0  1  2  3  4  5  6
[1, 3, 5, 7, 9, 15, 20]
 ^                  ^
left               right

2. Create a loop that finds the middle index between left and right.

is_found = False
my_array = [1, 3, 5, 7, 9, 15, 20]
target_value = 15
 
left = 0
right = len(my_array) - 1
 
while not(is_found):
	middle = (left + right) // 2

middle = (0+7)//2 = 3

 0  1  2  3  4  5  6
[1, 3, 5, 7, 9, 15, 20]
 ^        ^          ^
left    middle     right

3. Compare the element at middle with target_value, then shift left and right accordingly or break the loop if you have found the value.

is_found = False
my_array = [1, 3, 5, 7, 9, 15, 20]
target_value = 15
 
left = 0
right = len(my_array) - 1
 
while not(is_found):
	middle = (left + right) // 2
 
	if my_array[middle] == target_value:
		print("Found value in array!")
		is_found = True
		break
	elif my_array[middle] < target_value:
		left = middle + 1
	elif my_array[middle] > target_value:
		right = middle - 1

1st iteration:
middle = (0+7) // 2 = 3
          3
[1, 3, 5, 7, 9, 15, 20]
          ^
        middle

7 is less than 15, so we shift our left pointer to middle + 1. Right is kept as is.

left's new position = 3 + 1

 0  1  2  3  4  5  6
[1, 3, 5, 7, 9, 15, 20]
             ^      ^
           left   right

2nd iteration:
middle = (4+6)//2 = 5

 0  1  2  3  4  5  6
[1, 3, 5, 7, 9, 15, 20]
                ^
              middle

15 is equal to 15, so we print "Value found in array!" into output.

4. To prevent an infinite loop, we need to write a check when the value doesn’t exist. This is done by checking if the left pointer is greater than the right pointer. For example, we are looking for a target_value of 4 below.

is_found = False
my_array = [1, 3, 5, 7, 9, 15, 20]
target_value = 4
 
left = 0
right = len(my_array) - 1
 
while not(is_found):
	middle = (left + right) // 2
 
	if my_array[middle] == target_value:
		print("Found value in array!")
		is_found = True
		break
	elif my_array[middle] < target_value:
		left = middle + 1
	elif my_array[middle] > target_value:
		right = middle - 1
 
	# The check is here.
	if left > right:
		print("Not found")
		break

1st iteration:
middle = (0+7) // 2 = 3

7 is greater than 4, so we shift right pointer to middle - 1.

Right's new position = 2
 0  1  2  3  4  5  6
[1, 3, 5, 7, 9, 15, 20]
       ^
     right

2nd iteration:
middle = (0+2)//2 = 1

3 is less than 4, so we shift our left pointer to middle + 1

Left's new position = 2

3rd iteration:
middle = (2+2) // 2 = 2

5 is greater than 4, so we shift our right pointer to middle - 1.

Right's new position = 1

Left (2) cannot be greater than right (1), so we print "Not found" and break out of the loop.

Code sample

is_found =  False
my_array = [1, 3, 5, 7, 9, 15, 20]
target_value = 15
 
left = 0
right = len(my_array) - 1
 
while not(is_found):
    middle = (left + right) // 2
 
    if my_array[middle] == target_value:
        print("Found value in array!")
        is_found = True
	    break
    elif my_array[middle] < target_value:
        left = middle + 1
    elif my_array[middle] > target_value:
        right = middle - 1
    
    if left > right:
        print("Not found")
        break