Teaching Kids Programming – The Find Function/Algorithm for a List/Tuple in Python (Find vs Index)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Python is a powerful programming language that provides a variety of functions to help you work with data. Two of the most commonly used functions are the find and index functions. Both of these functions can be used to search for a specific substring in a string (the underlying algorithm to find substring in a string is KMP), but they have some key differences that make them better suited for different tasks.

The find function is used to search for a specific substring in a string. It returns the index of the first occurrence of the substring, or -1 if the substring is not found. This makes it useful for quickly finding a specific value in a string. The find function is also case-sensitive, meaning that it will only return the index of the first occurrence of the exact value you are searching for.

The index function will throw an exception (raise ValueError) if the item e.g. substring is not in the list or string. Notice that the list or tuple does not provide a find function.

Here is an example of using the find function:

1
2
3
4

s = "abcde"
print(s.find("b")) # return 1
print(s.find("X")) # return -1
print(s.find("C")) # return -1

s = "abcde"
print(s.find("b")) # return 1
print(s.find("X")) # return -1
print(s.find("C")) # return -1

And here is example of using the index function:

1
2
3
4

s = "abcde"
print(s.index("b")) # return 1
print(s.index("X")) # raise ValueError
print(s.index("C")) # raise ValueError

s = "abcde"
print(s.index("b")) # return 1
print(s.index("X")) # raise ValueError
print(s.index("C")) # raise ValueError

Both find and index support optional parameters (start and end) which specifies the range to search. For example:

1
2

s = "abcde"
print(s.find("b", 2, 3)) # return -1 as s[2:3] does not contain b

s = "abcde"
print(s.find("b", 2, 3)) # return -1 as s[2:3] does not contain b

To summarize, the find and index functions are two of the most commonly used functions in Python. The find function is used to search for a specific substring in a string, and it returns the index of the first occurrence of the value. The index function is similar to the find function, but it raise Exception of ValueError if the item is not in the list or substring.

The Find Function for a List or Tuple (Iterables) in Python

We can easily implement a Find function for List or Tuple (the Iterables) in Python using Linear Search (from left to right). If the iterable is sorted, we can also use Binary Search algorithm to improve the runtime complexity.

1
2
3
4
5
6
7

def find(iter, target, start = 0, end = -1):
    if end == -1:
        end = len(iter)
    for i in range(start, end):
        if iter[i] == target:
            return i
    return -1

def find(iter, target, start = 0, end = -1):
    if end == -1:
        end = len(iter)
    for i in range(start, end):
        if iter[i] == target:
            return i
    return -1

As we are performing the linear search, the time complexity is O(N). And we can use the next function to give us the first index of the occurence or minus one if not found:

1
2
3
4

def find(iter, target, start = 0, end = -1):
    if end == -1:
        end = len(iter)
    return next((i for i in range(start, end) if iter[i] == target), -1)

def find(iter, target, start = 0, end = -1):
    if end == -1:
        end = len(iter)
    return next((i for i in range(start, end) if iter[i] == target), -1)

If we want to throw ValueError Exception, we can too:

1
2
3
4
5
6
7

def index(iter, target, start = 0, end = -1):
    if end == -1:
        end = len(iter)
    x = next((i for i in range(start, end) if iter[i] == target), -1)
    if x == -1:
        raise ValueError(f"{target} not found")
    return x

def index(iter, target, start = 0, end = -1):
    if end == -1:
        end = len(iter)
    x = next((i for i in range(start, end) if iter[i] == target), -1)
    if x == -1:
        raise ValueError(f"{target} not found")
    return x

–EOF (The Ultimate Computing & Technology Blog) —