Learning Objectives

• Figure out what python development environment works for you
• Translate an algorithm into code
• Debug edge cases in an algorithm

Overview

We discussed in class how algorithms that take logarithmic time are very efficient in practice. In this lab, you will explore a logarithmic algorithm to quickly determine where a number is in a sorted list of numbers. It's easiest to see how this works with an example. Let's suppose we generate an array with 50 random numbers between 0 and 99. In this lab, we'll actually allow for repeat numbers. Here's some code below that uses a random seed (so you'll get the same results if you try it)

Now let's say we want to check to see if the number 40 is in there. We could just loop through every element in arr, but we can do something more efficient by asking some yes/no questions that help us split the range we have left to search continually in half.

First, we start with the full range, considering everything between indices low = 0 and high = 49, inclusive. Let's start by checking the one in the middle:

In this case, we see it's 35, which is less than the number we're looking for. Since the array is sorted, we can rule out everything including and below index 24 now. So we'll change our range to be low=25, high=49. Now let's check halfway in between these

We see that arr[37]=49, which is greater than our number, so we can rule out everything at index 37 and to the right of it, changing our range to be low=25, high=36

We keep doing this until low and high meet, and if we find our number at that index, it's in the array.

Below is a live demo to help you if you're a more visual person.

Your Task

Your task is to fill in a method called binarysearch, which takes in an array of numbers and a target number that is being searched. You can implement this either iteratively or recursively. Below is how you might start this off iteratively

Below is how you might start this off recursively (note the extra two parameters with "default values" starting off with the full range)

To test to make sure this is working properly, loop through the entire range of possible numbers in your list and print out three things:

1. The number
2. The result of binarysearch on that number
3. If the result is not -1, print out the array value at that index and check to make sure it's correct

For example, if you're looking at the array in the overview, which is

[0, 0, 1, 4, 5, 9, 9, 9, 12, 14, 17, 19, 19, 20, 21, 23, 25, 28, 29, 31, 31, 32, 32, 34, 35, 36, 36, 37, 38, 39, 39, 41, 42, 44, 46, 47, 47, 49, 53, 55, 57, 57, 58, 58, 64, 64, 65, 65, 65, 67, 67, 69, 70, 72, 74, 75, 77, 79, 79, 80, 81, 82, 83, 87, 87, 88, 88, 88, 88, 99]

You should print something like the following (though your indices may be slightly different for certain examples since there are repeats)

											
0 0 0
1 2 1
2 -1 
3 -1 
4 3 4
5 4 5
6 -1 
7 -1 
8 -1 
9 5 9
10 -1 
11 -1 
12 8 12
13 -1 
14 9 14
15 -1 
16 -1 
17 10 17
18 -1 
19 11 19
20 13 20
21 14 21
22 -1 
23 15 23
24 -1 
25 16 25
26 -1 
27 -1 
28 17 28
29 18 29
30 -1 
31 19 31
32 21 32
33 -1 
34 23 34
35 24 35
36 25 36
37 27 37
38 28 38
39 29 39
40 -1 
41 31 41
42 32 42
43 -1 
44 33 44
45 -1 
46 34 46
47 35 47
48 -1 
49 37 49
50 -1 
51 -1 
52 -1 
53 38 53
54 -1 
55 39 55
56 -1 
57 40 57
58 42 58
59 -1 
60 -1 
61 -1 
62 -1 
63 -1 
64 44 64
65 46 65
66 -1 
67 49 67
68 -1 
69 51 69
70 52 70
71 -1 
72 53 72
73 -1 
74 54 74
75 55 75
76 -1 
77 56 77
78 -1 
79 57 79
80 59 80
81 60 81
82 61 82
83 62 83
84 -1 
85 -1 
86 -1 
87 63 87
88 65 88
89 -1 
90 -1 
91 -1 
92 -1 
93 -1 
94 -1 
95 -1 
96 -1 
97 -1 
98 -1 
99 69 99
											
										

Tips

You should be very careful about what you change your low/high search range to based on how you choose your midpoint. Depending on how you implement binary search, there can be some serious pitfalls with infinite loops if you're not consistent with how you chose to round up or to round down if the midpoint is a decimal number. Here's how you'd round down if you wanted to do that

and here's how you'd round up