Two common search methods are linear, where we iterate through a list one-by-one till we find the value we want, or binary, where we apply a search formula/logic to more quickly find our target. There are benefits for both, and I wanted to go over them today.
When implementing a search algorithm it’s always important to consider the situation you’ll be in. Linear searches are considered better when you expect to find your target value at the beginning of a list, or if it’s a rather small list to begin with.
Binaries are better with larger data sets, and if it’s sorted. The search above has binary look at the middle index first. It’s value is 5, so it knows that’s too low, and that the target (#9) must be to the right. If the list wasn’t sorted than number 9 could be anywhere. The logic doesn’t apply. It is, however, much faster.
Let’s look at an example of linear search. For this example I’ll use a list of cities for a tour. Some cities will be on the list twice, so in this example I’ll want to return all the indices found. Can you form an idea on how I’d want to do that? Well in this case I’d want to return a list of indices.
Let’s set up my function.

def linear_search(search_list, target_value):
 matches = []

Great, now let’s look over the length of my search_list, so I have the correct number of indices to travel through, and if I have a match append it to matches.

for idx in range(len(search_list)): 
 if search_list[idx] == target_value:
 matches.append(idx)

From here I’ll return matches, but what if I don’t have any? Well in that case I’ll just return a valueError like such:

if matches:
 return matches
else:
 raise ValueError("{0} not in list".format(target_value))

Binary’s are a little more complicated, but fortunately we can use a recursion operation so we only have to write a base case to exit the loop, and how to fully perform the binary operation once.
Our binary search will take four parameters. The sorted list, the left pointer, the right pointer, and the target we’re looking for.
The left pointer is typically 0, and the right pointer will be the length of the list.

def binary_search(sorted_list, left_pointer, right_pointer, target):

Let’s put in a safety measure in case the list is empty.

if left_pointer >= right_pointer:
 return "value not found"

>Next to implement some logic for the binary search. I’ll want to find the middle index since that’s where I’ll start looking, and it’s value.

mid_idx = (left_pointer + right_pointer) // 2
mid_val = sorted_list[mid_idx]

Now if I get lucky on my first look, I’ll just want to return that index. However if the middle index is greater than the target I’m looking for I’ll call the search again, but set the right_pointer to be the middle index since I’m looking left.
If I’m looking to the right of the list I’ll change the left_pointer to start from the middle index (plus one because I already looked at the middle index).

if mid_val == target:
 return mid_idx
if mid_val > target: 
 return binary_search(sorted_list, left_pointer, mid_idx, target)
if mid_val < target:
 return binary_search(sorted_list, mid_idx + 1, right_pointer, target)

And that’s it! Here it is in it’s full form:

It’s always a good idea when building a search algorithm to break your needs to their most basic steps, and build from there. It is possible to write this code as an iterative operation. Feel free to take a crack at it if you want to test your mental metal. Happy coding.