Search an Element in a List or Tuple Program in Python, C and Java

What You Will Learn

• The problem statement
• Program 1: Linear search
• Program 2: Binary search
• Linear search versus binary search
• Other ways: the in operator, index(), recursion, bisect and more
• Common mistakes, practice questions and FAQ

Problem Statement

Input a list or tuple of elements and search for a given element in it.

The user enters the numbers and the key to search. The program prints the index where the key was found, or a message that the key is not present. The interactive tool above accepts 1 to 12 numbers from -999 to 999, and it lets you switch between a list and a tuple and between the two search methods.

Remember that an index starts at 0. If the key is the first element, the program prints index 0. The position, counting from 1, is always the index plus one.

Program 1: Linear Search

Linear search, also called sequential search, is the simplest method. Start at the first element and compare each element with the key, one after the other. If an element matches, stop and report its index. If the end of the list is reached, the key is not there.

Logic:

• Read the numbers into nums, read the key, and find n.
• Set pos = -1. The value -1 means “not found yet”, because -1 can never be a real index.
• Loop i from 0 to n − 1. If nums[i] == key, set pos = i and break.
• After the loop, if pos != -1 print the index, otherwise print “not found”.

The program works for a list and for a tuple, because searching only reads the elements. In C and Java, the same loop runs over an array.

Python program

nums = list(map(int, input("Enter numbers separated by spaces: ").split()))
key = int(input("Enter the number to search: "))
n = len(nums)
pos = -1
for i in range(n):
    if nums[i] == key:
        pos = i
        break
if pos != -1:
    print(key, "found at index", pos)
else:
    print(key, "not found in the list")

#include <stdio.h>
int main() {
    int n, key;
    printf("How many numbers? ");
    scanf("%d", &n);
    int nums[100];
    printf("Enter the numbers: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    printf("Enter the number to search: ");
    scanf("%d", &key);
    int pos = -1;
    for (int i = 0; i < n; i++) {
        if (nums[i] == key) {
            pos = i;
            break;
        }
    }
    if (pos != -1) {
        printf("%d found at index %d\n", key, pos);
    } else {
        printf("%d not found in the list\n", key);
    }
    return 0;
}

import java.util.Scanner;
public class SearchProgram {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("How many numbers? ");
        int n = sc.nextInt();
        int[] nums = new int[n];
        System.out.print("Enter the numbers: ");
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.print("Enter the number to search: ");
        int key = sc.nextInt();
        int pos = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] == key) {
                pos = i;
                break;
            }
        }
        if (pos != -1) {
            System.out.println(key + " found at index " + pos);
        } else {
            System.out.println(key + " not found in the list");
        }
    }
}

Sample output (key present):

Enter numbers separated by spaces: 10 25 7 31 18
Enter the number to search: 31
31 found at index 3

Another run (key absent):

Enter numbers separated by spaces: 10 25 7 31 18
Enter the number to search: 99
99 not found in the list

Dry run for [10, 25, 7, 31, 18], key = 31:

The loop stops with a break, so only 4 of 5 elements were checked. The key is at index 3.

Dry run for [10, 25, 7, 31, 18], key = 99:

All 5 elements were checked and none matched, so pos stays -1 and the program prints “not found”.

Because of the break, the program stops at the first match. If the key appears several times, as in [3, 3, 3], it reports the first index, which is 0.

Program 2: Binary Search

Binary search is much faster, but it needs a sorted list. Think of finding a word in a dictionary: you open the book in the middle, see whether your word comes before or after that page, and throw away the half you do not need. You repeat this on the remaining half.

Logic:

• Sort the list, because binary search only works on sorted data.
• Set low = 0, high = n - 1 and pos = -1.
• While low <= high: find the middle, mid = (low + high) // 2.
• If nums[mid] == key, set pos = mid and stop.
• If nums[mid] < key, the key can only be on the right, so set low = mid + 1.
• Otherwise the key can only be on the left, so set high = mid - 1.
• When low becomes bigger than high, the range is empty and the key is not in the list.

The program sorts a copy first with sorted() in Python, a small bubble sort in C and Arrays.sort() in Java. The index it prints belongs to the sorted list, not to the order you typed.

Python program

nums = list(map(int, input("Enter numbers separated by spaces: ").split()))
key = int(input("Enter the number to search: "))
n = len(nums)
nums = sorted(nums)
low = 0
high = n - 1
pos = -1
while low <= high:
    mid = (low + high) // 2
    if nums[mid] == key:
        pos = mid
        break
    elif nums[mid] < key:
        low = mid + 1
    else:
        high = mid - 1
if pos != -1:
    print(key, "found at index", pos)
else:
    print(key, "not found in the list")

#include <stdio.h>
int main() {
    int n, key;
    printf("How many numbers? ");
    scanf("%d", &n);
    int nums[100];
    printf("Enter the numbers: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    printf("Enter the number to search: ");
    scanf("%d", &key);
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                int t = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = t;
            }
        }
    }
    int low = 0, high = n - 1, pos = -1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (nums[mid] == key) {
            pos = mid;
            break;
        } else if (nums[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    if (pos != -1) {
        printf("%d found at index %d\n", key, pos);
    } else {
        printf("%d not found in the list\n", key);
    }
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
public class SearchProgram {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("How many numbers? ");
        int n = sc.nextInt();
        int[] nums = new int[n];
        System.out.print("Enter the numbers: ");
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.print("Enter the number to search: ");
        int key = sc.nextInt();
        Arrays.sort(nums);
        int low = 0, high = n - 1, pos = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == key) {
                pos = mid;
                break;
            } else if (nums[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        if (pos != -1) {
            System.out.println(key + " found at index " + pos);
        } else {
            System.out.println(key + " not found in the list");
        }
    }
}

Sample output (key present):

Enter numbers separated by spaces: 5 8 12 20 33 41 57
Enter the number to search: 41
41 found at index 5

Another run (key absent):

Enter numbers separated by spaces: 9 1 8 2 7 3
Enter the number to search: 4
4 not found in the list

Dry run for [5, 8, 12, 20, 33, 41, 57], key = 41:

Found at index 5 after 2 comparisons.

Dry run for [5, 8, 12, 20, 33, 41, 57], key = 6:

Now low is bigger than high, so the range is empty. The key is not in the list (3 comparisons).

Dry run for [9, 1, 8, 2, 7, 3], key = 7:

First the list is sorted: [1, 2, 3, 7, 8, 9].

Found at index 3 after 3 comparisons.

Each step throws away half of the remaining elements, so the list shrinks very fast. Seven elements need at most 3 comparisons.

Linear Search Versus Binary Search

The worst-case number of comparisons is shown below. For 10, 100 and 1,000 elements the binary search figures were measured by running the search on every possible key. The last row follows from the same rule.

For a million sorted elements, binary search needs at most 20 comparisons, while linear search may need a million. The price is the sorting step. Sorting costs more than one linear search, so for a single search on unsorted data a linear scan is cheaper. Binary search pays off when you sort once and search many times.

Other Ways to Write the Program

Method 3: The in operator and index() in Python

Python can search without any loop. The in operator tells you whether the key is present, and index() returns the first position. Calling index() on a missing key raises a ValueError, so check with in first. Both work on lists and tuples.

nums = list(map(int, input("Enter numbers separated by spaces: ").split()))
key = int(input("Enter the number to search: "))
if key in nums:
    print(key, "found at index", nums.index(key))
else:
    print(key, "not found in the list")

Sample output:

Enter numbers separated by spaces: 10 25 7 31 18
Enter the number to search: 25
25 found at index 1

Method 4: While loop

The same linear search with a while loop shows the counter clearly. You must increase i yourself, otherwise the loop never ends.

nums = list(map(int, input("Enter numbers separated by spaces: ").split()))
key = int(input("Enter the number to search: "))
i = 0
pos = -1
while i < len(nums):
    if nums[i] == key:
        pos = i
        break
    i = i + 1
if pos != -1:
    print(key, "found at index", pos)
else:
    print(key, "not found in the list")

Sample output:

Enter numbers separated by spaces: 10 25 7 31 18
Enter the number to search: 18
18 found at index 4

Method 5: Using a function

A function that returns the index, or -1, can be reused for any list or tuple. Returning from inside the loop replaces the break.

def linear_search(items, key):
    for i in range(len(items)):
        if items[i] == key:
            return i
    return -1
nums = list(map(int, input("Enter numbers separated by spaces: ").split()))
key = int(input("Enter the number to search: "))
pos = linear_search(nums, key)
if pos != -1:
    print(key, "found at index", pos)
else:
    print(key, "not found in the list")

Sample output:

Enter numbers separated by spaces: 10 25 7 31 18
Enter the number to search: 7
7 found at index 2

Method 6: Finding every occurrence

To report all positions of a repeated key, remove the break and print inside the loop. A flag tells you at the end whether anything was found.

nums = list(map(int, input("Enter numbers separated by spaces: ").split()))
key = int(input("Enter the number to search: "))
found = False
for i in range(len(nums)):
    if nums[i] == key:
        print(key, "found at index", i)
        found = True
if not found:
    print(key, "not found in the list")

Sample output:

Enter numbers separated by spaces: 7 3 7 1 7
Enter the number to search: 7
7 found at index 0
7 found at index 2
7 found at index 4

Method 7: Counting occurrences

A small change gives the number of times the key appears, which is the same as nums.count(key) in Python.

nums = list(map(int, input("Enter numbers separated by spaces: ").split()))
key = int(input("Enter the number to search: "))
count = 0
for x in nums:
    if x == key:
        count = count + 1
print(key, "appears", count, "time(s)")

Sample output:

Enter numbers separated by spaces: 7 3 7 1 7
Enter the number to search: 7
7 appears 3 time(s)

Method 8: Binary search using recursion

Binary search can also call itself on the smaller range. The base case is an empty range (low greater than high), which means “not found”.

def binary_search(a, key, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if a[mid] == key:
        return mid
    elif a[mid] < key:
        return binary_search(a, key, mid + 1, high)
    else:
        return binary_search(a, key, low, mid - 1)
nums = list(map(int, input("Enter numbers separated by spaces: ").split()))
key = int(input("Enter the number to search: "))
nums = sorted(nums)
pos = binary_search(nums, key, 0, len(nums) - 1)
if pos != -1:
    print(key, "found at index", pos)
else:
    print(key, "not found in the list")

Sample output:

Enter numbers separated by spaces: 5 8 12 20 33 41 57
Enter the number to search: 20
20 found at index 3

Method 9: The bisect module

Python ships a binary search helper. bisect_left returns the place where the key is or would be inserted, so you check that place afterwards.

nums = list(map(int, input("Enter numbers separated by spaces: ").split()))
key = int(input("Enter the number to search: "))
import bisect
nums = sorted(nums)
i = bisect.bisect_left(nums, key)
if i != len(nums) and nums[i] == key:
    print(key, "found at index", i)
else:
    print(key, "not found in the list")

Sample output:

Enter numbers separated by spaces: 5 8 12 20 33 41 57
Enter the number to search: 57
57 found at index 6

Variation: a fixed tuple

t = (10, 25, 7, 31, 18)
key = 31
if key in t:
    print(key, "found at index", t.index(key))
else:
    print(key, "not found in the tuple")

Output:

31 found at index 3

Variation: searching a character in a string

A string is also a sequence, so the same loop finds a character.

text = input("Enter a string: ")
ch = input("Enter the character to search: ")
pos = -1
for i in range(len(text)):
    if text[i] == ch:
        pos = i
        break
if pos != -1:
    print(ch, "found at index", pos)
else:
    print(ch, "not found in the string")

Sample output:

Enter a string: hello world
Enter the character to search: o
o found at index 4

Common Mistakes

1. Using binary search on an unsorted list. For [9, 1, 8, 2, 7, 3] and the key 2, which is in the list, a binary search without sorting returns -1, because it throws away the wrong half. Always sort first, or use linear search.
2. Forgetting that the index belongs to the sorted list. After sorting, the elements move. Binary search reports the index in the sorted order.
3. Printing “not found” inside the loop. If you print it in the else branch for every non-matching element, you print it many times. Decide after the loop, using pos or a flag.
4. Using 0 as the “not found” value. Index 0 is a valid index, so a not-found value of 0 is confusing. Use -1.
5. Using the wrong condition in binary search. The loop must run while low <= high. With low < high the last remaining element is never checked.
6. Not moving past mid. Writing low = mid or high = mid can make the loop run forever. Use mid + 1 and mid - 1.
7. Calling index() on a missing key. Python raises a ValueError. Check with in first, or use the loop version.
8. Comparing text with a number. If the key is read without int, the string “31” never equals the number 31, and the program always says “not found”.

Practice Questions

1. Print the position (counting from 1) of the key instead of the index.
2. Print all the positions where the key occurs.
3. Count how many comparisons the program made before it stopped.
4. Search for a name in a list of names.
5. Find the first element in a list that is greater than a given number.
6. Write binary search to find the first occurrence when the key appears many times in a sorted list.

Frequently Asked Questions

How do you search for an element in a list in Python?

Use the in operator to check if it exists and index() to find its position. Or write a loop that compares each element with the key and stops at the first match.

What is linear search?

Linear search checks the elements one by one from the start until it finds the key or reaches the end of the list. It works on any list, sorted or not.

What is binary search?

Binary search looks at the middle element of a sorted list and throws away the half that cannot contain the key. It repeats this until the key is found or nothing is left.

Does binary search work on an unsorted list?

No. The decision to throw away half of the list is only correct when the list is sorted. Sort it first, or use linear search.

Which is faster, linear or binary search?

Binary search is much faster on large sorted data: about 20 comparisons for a million elements, against up to a million for linear search. For a small or unsorted list, linear search is simpler and often good enough.

What is the time complexity of linear and binary search?

Linear search is O(n) and binary search is O(log n). Both use O(1) extra space in the loop versions.

Why do we use -1 when the element is not found?

Valid indexes are 0 or more, so -1 can never be a real index. It is a safe signal for “not found”.

Can I search in a tuple the same way?

Yes. A tuple supports indexing, in, index() and loops just like a list. Only changing a tuple is not allowed, and searching never changes anything.

What happens if the element appears more than once?

Linear search with a break reports the first index. Binary search may report any one of the matching positions. Remove the break to collect all positions with linear search.

How many comparisons does binary search need?

At most the number of times you can halve n, plus one. That is 4 for 10 elements, 7 for 100, 10 for 1,000 and 20 for 1,000,000.