Editor

Python Program to Find the First and Last Position of an Element

Intermediate · Searching and sorting

When a value appears several times in a list, its first occurrence is the lowest index where it appears and its last occurrence is the highest. This program finds both with one pass through the list, and the alternatives show the fast binary search version used for sorted lists.

Program

first_and_last_occurrence.py
numbers = [5, 7, 7, 8, 8, 8, 10]
target = 8 # or: target = int(input("Enter the number to find: "))
first = -1 # -1 means "not found yet"
last = -1
for i in range(len(numbers)):
if numbers[i] == target:
if first == -1:
first = i # the first match is recorded once
last = i # the last match keeps moving forward
print("List:", numbers)
if first == -1:
print(target, "is not in the list")
else:
print(f"First position of {target}: index {first}")
print(f"Last position of {target}: index {last}")
Output
List: [5, 7, 7, 8, 8, 8, 10]
First position of 8: index 3
Last position of 8: index 5

How it works

  1. first and last start at -1, a value that can never be a real index.
  2. The first time the target is found, first is still -1, so it is set to that index and never changed again.
  3. last is updated at every match, so after the loop it holds the index of the final one.
  4. If the target never appears, both stay -1 and the program says so.
  5. This works for any list, sorted or not.

Other ways to write it

Binary search on a sorted list

Binary search on a sorted list
def find_edge(numbers, target, first):
low, high = 0, len(numbers) - 1
found = -1
while low <= high:
mid = (low + high) // 2
if numbers[mid] < target:
low = mid + 1
elif numbers[mid] > target:
high = mid - 1
else:
found = mid # a match: remember it and keep looking
if first:
high = mid - 1 # is there an earlier one?
else:
low = mid + 1 # is there a later one?
return found
numbers = [5, 7, 7, 8, 8, 8, 10] # must be sorted
print("First 8 at index", find_edge(numbers, 8, True))
print("Last 8 at index", find_edge(numbers, 8, False))
Output
First 8 at index 3
Last 8 at index 5

An ordinary binary search stops at any match. This one remembers the match and keeps searching to the left (for the first) or to the right (for the last).

Using index() on the list and its reverse

Using index() on the list and its reverse
numbers = [5, 7, 7, 8, 8, 8, 10]
target = 8
if target in numbers:
first = numbers.index(target)
# index() in the reversed list counts from the end
last = len(numbers) - 1 - numbers[::-1].index(target)
print("First index:", first, "| Last index:", last)
else:
print(target, "is not in the list")
Output
First index: 3 | Last index: 5

index() only finds the first match, so searching the reversed list finds the last one, counted from the end, and the subtraction turns it back into a normal index.

Try it yourself

Set target to 6 to see the "not in the list" message, then to 10.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises