Linear Searching in Scala

Input: nums = [1, 2, 4, 5], value = 4
Output: 2
Explanation: nums[2] is 4

We should try out each element in nums until we find one equal to value and return its index. How can we achieve this?

With a for loop, of course! We can use a variable num to iterate through the elements and an if statement to check if num == value:

for each num in nums:
	if num == value:
    # Solution found! But...

This is how we look for value in nums, but there's a problem. The problem asks us to return the index of that element, and by iterating like this we only know the value of the current element, not its index. How can we fix this?

We should use another method of iterating through an array: by indices! Let's use an index variable i to go through every index between 0 and nums.length - 1:

for i : 0 -> nums.length - 1:
	# index is i, value is nums[i]
  	if nums[i] == value:
    		return i

What if we don't have any element equal to value? Where should we return -1?

for i : 0 -> nums.length - 1:
	# index is i, value is nums[i]
  	if nums[i] == value:
    		return i

# Here:
return -1

If we reach the line with the comment, this means the for loop terminated naturally without returning any index. If we have had returned an index, we wouldn't even be executing this line of code as the program would have finished.

We have a for loop that performs exactly n iterations (where n is the length of nums), thus the Time Complexity is O(n).
The only extra space we use is the iterator variable i inside the loop, thus the Extra Space used is O(1).