Help support the author by donating or purchasing a copy of the book (not available yet)



Chapter 7 - Linear Search

In this chapter you're going to code your first algorithm. We'll take a look at the linear search algorithm.

Linear search (or sequential search) is a method to find an element in something. That something may be a string, a file or a list. The element we are searching for could be anything (a letter, a number, a word, etc).

(Usually) we are searching for the position of the element we want. Therefore, in some cases, the element we are searching for may not exist and we need our algorithm to be able to handle that.

Linear search is commonly used in computer science and is an easy algorithm to understand and write and it's perfect for us at this stage.

7.2 Linear search using while

In technical terms, we are searching for the position of some element Q that satisfies some property P.

In the general case, we can achieve this as follows:

i = 0
while i < N and not P:
    i += 1

What we want is the position of the element Q that satisfies some property P so we continue to search as long as that property P is not satisfied and we stop when it is.

Let's look at an example to help clarify. In this example we want to find the position of the first occurrence of the letter "W":

s = "Hello World"

i = 0
while i < len(s) and s[i] != "W":
    i += 1

What we do here is, begin at index 0 ("H") and continue through the string, checking each index until "W" is found and that is linear search.

Now we have another problem. There are two conditions in the while loop. Either "W" is found and we exit the loop or we search the entire string and "W" is not found. How do we know which condition caused the loop to terminate?

If condition 1 (i < len(s)) is True then "W" was found as we clearly didn't reach the end of the string OR condition 1 is False in which case we did reach the end of the string and "W" was not found.

We can check this simply:

s = "Hello World"

i = 0
while i < len(s) and s[i] != "W":
    i += 1
    
if i < len(s):
    print("The letter 'W' was found at position " + str(i) + " in the string")
else:
    print("The letter 'W' was not found in the string")

This is usually how linear search works, however, we can have more complicated versions which we will get to in the next section.

7.3 - Examples

Important Note:

If you have some previous experience of programming you may be wondering why I'm using while loops to do this? I'm doing it this way to promote computational thinking and in the future we will move away from this approach.

In this section I'm going to go through some more examples of linear search using while loops, some of which may get a little complicated so spend some time going through them.

For our first example, let's recreate the lstrip() string method.

s = input()

i = 0
while i < len(s) and s[i] == " ":
    i += 1
    
if i < len(s):
    print(s[i:])
else:
    print("No alpha-numeric characters exist in this string")

The above program will strip all leading white space characters.

Let's take a look at a more difficult example. For this problem we want the user to input a string and print out that string, removing all leading and trailing whitespace and only one white space character between each word.

# INPUT
"    This    is a   string       with  lots  of whitespace  "

# OUTPUT
"This is a string with lots of whitespace"

This is difficult to solve and can remember being given this problem when I was learning to program. To solve this problem we'll need to nest while loops inside each other.

s = input()
output = ""

i = 0
while i < len(s):
    # Find a non whitespace character (start of a word)
    while i < len(s) and s[i] == " ":
        i += 1
    
    j = i
    if i < len(s):
        # Find the end of that word
        while j < len(s) and s[j] != " ":
            j += 1
        
        # Build up a string from the original without the excess whitespace
        output += " " + s[i:j]
    
    i = j + 1


# Print out the final string
print(output[1:])

I'm not going to explain this, I want you to work through it. Take a simple input string to help you walk through the program.

7.4 - Exercises

Important Note:

The solutions to some of these exercises require thinking outside-the-box. Don't expect to arrive at a solution immediately!

Question 1

Write a program that takes a string from the user and prints the first number encountered along with it's position.

You can assume the number is a single digit

# EXAMPLE INPUT
"This is chapter 7 of the book"

# EXAMPLE OUTPUT
"7 16"

# EXAMPLE INPUT
"There are no digits here"

#EXAMPLE OUTPUT
"No digits in string"

Question 2

Building upon the previous exercise, write a program that takes a string as input from the user and prints the first number encountered along with the starting position of the number.

Working through this question on paper would be a good idea!

# EXAMPLE INPUT
"This chapter has 1208 words in it!"

# EXAMPLE OUTPUT
"1208 17"

# EXAMPLE INPUT
"There is no numbers here"

# EXAMPLE OUTPUT
"No numbers in string"

Question 3

Write a program that takes a string as input from the user. The string will consist of digits and your program should print out the first repdigit. A repdigit is a number where all digits in the number are the same. Examples of repdigits are 22, 77, 2222, 99999, 444444.

# EXAMPLE INPUT
"34 74 86 34576 47093 3 349852 777 9082"

# EXAMPLE OUTPUT
"777"

# EXAMPLE INPUT
"98 3462 245 87658"

# EXAMPLE OUTPUT
"No repdigit in string"

Question 4

If you open a browser and go to any web page that has text on it and press Ctrl+f, a search box will pop up. You can type any word in this search box and all occurrences of that word on the page are highlighted. This doesn't use linear search, it uses something called regular expressions (don't worry about what they are). As well as the occurrences of the word being highlighted, you are also told how many times the word occurs.

You are to write a program which mimics this behaviour. Your program should take a string as input from the user and then a second string as input which is the word the user wants to search for. Your program should print out how many times the word occurs in the string.

Assume that it still counts if the word you're searching for is embedded in another word, for example if the user was searching for the word "search":

search and searching <- you can count this as 2 occurrences

# EXAMPLE INPUT
"In this type of search, a sequential search is made over all items one by one"
"search"

# EXAMPLE OUTPUT
2

# EXAMPLE INPUT
"There wont be an occurrence here"
"python"

# EXAMPLE OUTPUT
0


Help support the author by donating or purchasing a copy of the book (not available yet)



Previous Chapter - Next Chapter