Problem

Given an integer array arr of size n and a target value x, return the index of the first occurrence of x in arr. If x is not present, return -1. The array is not sorted, so binary search does not apply.

Input / Output

• Input: array arr, integer x.
• Output: index (0-based) or -1.

Examples

Example 1 Input: arr = [4, 2, 7, 2, 9], x = 2 Output: 1

Example 2 Input: arr = [4, 2, 7], x = 5 Output: -1

Example 3 Input: arr = [1], x = 1 Output: 0

Constraints

• 1 <= n <= 10^5

Approach

Scan the array from left to right and return the first index whose value equals x. There is no shortcut when the data is unsorted: any algorithm must, in the worst case, inspect every element, so O(n) is optimal.

Discussion points the interviewer may steer towards:

• Sentinel search: temporarily place x at arr[n-1] so the loop needs no bounds check, then restore it — a micro-optimisation from older textbooks.
• Multiple queries: if the same array is searched many times, preprocess it — sort (O(n log n)) then binary search each query in O(log n), or build a hash map from value to first index for O(1) lookups.
• Return all occurrences or the last occurrence (scan from the right).

Complexity

• Time: O(n) worst case, O(1) best case.
• Space: O(1)

Reference solution (Python)

def linear_search(arr, x):
    for i, v in enumerate(arr):
        if v == x:
            return i
    return -1

Test cases

Input	Expected
[4,2,7,2,9], x=2	1
[4,2,7], x=5	-1
[1], x=1	0
[3,3,3], x=3	0