Finding an Object in a Python Array – Find the First, Last, and All Occurences of Objects in an Array

Feature Img Find Occurrence

Today in this tutorial, we will be finding the first, last, and all occurrences of an element in an array with the help of Recursion.

Before going into any of the problem statements, let us first understand what Recursion is. If you want to learn about Recursion, a link is provided to know about Recursion.

Learn about Recursion here: Python Recursion


Finding the First Occurence of the Element

Let’s begin by looking for the first occurrence of the element in a Python array. We aim to find the very first position at which the element occurs in a list of elements (array).

For Example:
Array Given ==> [1,2,3,4,2]
First Occurence ==> 2

To find the solution to the problem we would take the following steps:

Step 1 :  Check if list is empty then return that list is empty
Step 2 : Check if there is only one element then check the first element with X and return the answer if found
Step 3 : For more than one element, we will check if the first element is equal to X if found then return 
Step 4 : Otherwise recursively go by slicing the array and incrementing and decremementing the itrerator and n value (size of array ) respectively
Step 5 :  Repeat until the element is found or not

The code implementation of the above-mentioned steps is shown below:

def find_first(arr,n,x,itr):

    # check if list is empty
    if(n==0):
        print("List empty!")
        return

    # Only one element
    elif(n==1):
        if(arr[0]==x):
            print("Element present at position 1")
        else:
            print("Element not found")
        return

    # More than one element
    else:
        if(arr[0] == x):
            print("Found at position: ", itr+1)
        else:
            find_first(arr[1:],n-1,x,itr+1)
        return

arr = [1,2,3,4,5,2,10,10]
n  = len(arr)
x = 10
itr = 0
find_first(arr,n,x,itr)

Output:

Found at position:  7

Finding the Last Occurence of an Object

Next, we’ll try to find the last occurrence of the element using Python. We aim to find the very last position at which the element occurs in a list of elements (array).

For Example:
Array Given ==> [1,2,3,4,2]
Last Occurence ==> 5

To find the solution to the problem we would take the following steps:

Step 1 :  Check if list is empty then return that list is empty
Step 2 : Check if there is only one element then check the first element with X and return the answer if found
Step 3 : For more than one element, we will check if the last element is equal to X if found then return 
Step 4 : Otherwise recursively go by slicing the array and decremementing both the iterator and n value (size of array ) 
Step 5 :  Repeat until the element is found or not

Implementing the above steps in Python

def find_first(arr,n,x,itr):

    # check if list is empty
    if(n==0):
        print("List empty!")
        return

    # Only one element
    elif(n==1):
        if(arr[0]==x):
            print("Element present at position 1")
        else:
            print("Element not found")
        return

    # More than one element
    else:
        if(arr[n-1] == x):
            print("Found at position: ", itr+1)
        else:
            find_first(arr[:-1],n-1,x,itr-1)
        return

arr = [1,2,3,4,5,2,3,2,3,2,10,10]
n  = len(arr)
x = 2
itr = n - 1
find_first(arr,n,x,itr)

Output:

Found at position:  10

Finding All Occurences of an Object

Here we aim to find all the positions at which the element occurs in a list of elements (array). The occurrences include the first, last, and any middle positions of the element in the array.

For Example:
Array Given ==> [1,2,3,4,2]
All Occurences ==> 2 5

To find the solution to the problem we would take the following steps:

Step 1 :  Check if list is empty then return that list is empty
Step 2 : Check if there is only one element then print the position of the element and return
Step 3 : For more than one element, we will check if the first element is equal to X if found then print and keep on recursively calling the function again by slicing the array and decremementing n value (size of array ) and incrementing the value of iterator
Step 5 :  Repeat until all the elements are encountered.

Implementing the above steps in Python

def find_first(arr,n,x,itr):

    # check if list is empty
    if(n==0):
        print("List empty!")
        return

    # Only one element
    elif(n==1):
        if(arr[0]==x):
            print(itr+1,end=" ")
        else:
            print("Element not found")

    # More than one element
    else:
        if(arr[0] == x):
            print(itr+1,end=" ")
        find_first(arr[1:],n-1,x,itr+1)

arr = [1,2,10,3,4,10,5,2,10,2,3,10]
n  = len(arr)
x = 10
itr = 0
print("Found at position: ",end="") 
find_first(arr,n,x,itr)

Output:

Found at position: 3 6 9 12 

Conclusion

So by end of this tutorial, we are familiar with finding an elements’ first, last, and all occurrences in a given array. Hope you understood the logic!

Thank you for reading! Happy learning! 😇