# Topic #14 – Searching¶

## You are *here*¶

- At this point in the course you should feel like:
The Python programming environment is a relatively familiar sight (Colab, IPython, PyCharm, Spyder)

You’re growing more comfortable using Python to accomplish small tasks

If you saw a simple Python program, you could figure out, more or less, what it does without having to run it

You know what a variable is

You know what a data

*type*is (particularly: strings, integers, booleans and floating point numbers)You know that strings are

*special*You know that you have to be

*very careful*with floating point valuesYou know what lists, arrays, tuples and dictionaries are and how they differ

You know about mutability and aliasing in data structures

You know how to use

`if`

statements to*conditionally*execute codeYou know how to write, and call, functions

You know what a “pure” function is and what “side effect” means.

You know how (and when) to use both

`for`

loops and`while`

loopsYou know how to develop your own code, one small step at a time, testing along the way.

You know how to debug and use a debugger

You know how to comment your code so you can read it next week.

You know how to get data into and out of python with files.

You know that exceptions are a thing

You know how to use objects

You know how to make your own objects

## Back to fundamentals¶

We’ve actually gone pretty deep into topics, so it’s time to go back to some basic CS.

We have a lot of tools in our tool belt

We have a solid understanding of some

*data structures*We’re kinda’ missing out on the

*algorithms*at this pointWe’ll actually look at some real, but challenging problems

We will look at some

*good*ways to solve these problemsWe’ll look at

*bad*ways too.

## Searching (again)¶

I know I’ve beaten this into you at this point, but…

*linear*search…

Activity

Write a function `find_element(element, list)`

that returns `True`

if `element`

is in `list`

and `False`

otherwise.

You may *not* use the `in`

operator (that’s cheating!)

Nothing new here… you already know how to search an unordered list.

Activity

Discuss this with your neighbours:

On average, how many iterations through your loop does your function make?

How about in the worst case?

Is your solution the best possible?

Might there exist some super clever algorithm that is somehow better (faster) than yours?

These kinds of questions are getting you closer to computer

*science*and further from straight “programming”.

Activity

James will now guess a number between 0 and 1023 in less than 10 guesses.

Activity++

Think of how a function `find_element(element,sorted_list)`

that returns `True`

if `element`

is in `sorted_list`

and `False`

otherwise would be written.

You may *not* use the `in`

operator (that’s still cheating!).

This time, I *promise* you that I will only call your function on a list which is *already sorted*. Do this in a group. It’s not an easy one.

If you can, code up the solution.

- Now we need to ask the same questions as before:
On average, how many iterations through your loop does your function make?

How about in the worst case?

Is your solution the best possible?

Might there exist some super clever algorithm that is somehow better (faster) than yours?

- This is a
*very*common pattern in developing algorithms: The more

*general*your problem is, the slower the solution is.The more you know about the

*structure*of your problem (e.g., “the list is always sorted”), the more opportunities you have to use that knowledge to make the solution faster.

- This is a

## Quick look at different programming languages¶

Here are a few linear searchers in different programming languages.

### Python¶

```
1def linear_search(a_list, thing):
2 for i in range(len(a_list)):
3 if a_list[i] == thing:
4 return True
5 return False
```

### C++¶

```
1bool linear_search(int a_list[], int n, int thing){
2 for(int i = 0 ; i < n ; i++){
3 if(a_list[i] == thing){
4 return true;
5 }
6 }
7 return false;
8}
```

### Java¶

```
1public boolean linear_search(int[] a_list, int thing){
2 for(int i = 0 ; i < a_list.length ; i++){
3 if(a_list[i] == thing){
4 return true;
5 }
6 }
7 return false;
8}
```

### Haskell¶

```
1linear_search :: Eq a => [a] -> a -> Bool
2linear_search [] _ = False
3linear_search (x:xs) y = x==y || linear_search xs y
```

## For next class¶

Keep reading chapter 14 of the text