Swift Coding Test Course, Finding the Desired Integer

Problem Description

You are given an integer array numbers. Write a function to check if a specific integer target exists in this array. If it exists, return the index of that integer; if not, return -1.

func findTarget(numbers: [Int], target: Int) -> Int

Input

• numbers: An array of integers (1 ≤ length of numbers ≤ 10⁶)
• target: The integer you want to find (-10⁹ ≤ target ≤ 10⁹)

Output

If target exists, return the corresponding index; otherwise, return -1.

Examples

Example 1

Input: numbers = [1, 2, 3, 4, 5], target = 3
Output: 2

Example 2

Input: numbers = [5, 6, 7, 8, 9], target = 1
Output: -1

Solution Approach

To solve this problem, one must think of how to find the index of target within the array. A basic method is linear search using a loop, and if the array is sorted, binary search can be used.

1. Linear Search

Linear search is a method where you check each element one by one from the beginning to the end of the array to find target. The time complexity is O(n) depending on the length of the array.

2. Binary Search

Binary search is much more efficient when the array is sorted. This method reduces the search range by half based on the middle index of the array to find target. The time complexity in this case is O(log n).

Implementation

First, we will implement linear search and then also implement binary search.

Linear Search Implementation

func findTarget(numbers: [Int], target: Int) -> Int {
    for (index, number) in numbers.enumerated() {
        if number == target {
            return index
        }
    }
    return -1
}

Binary Search Implementation

func binarySearch(numbers: [Int], target: Int) -> Int {
    var left = 0
    var right = numbers.count - 1

    while left <= right {
        let mid = (left + right) / 2
        if numbers[mid] == target {
            return mid
        } else if numbers[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

Test Cases

We will run a few cases to test the function we have written.

let numbers = [1, 2, 3, 4, 5]
let target1 = 3
let target2 = 6

print(findTarget(numbers: numbers, target: target1)) // 2
print(findTarget(numbers: numbers, target: target2)) // -1

Performance Evaluation

Linear search is simple but, in the worst case, requires searching through all elements, taking an average of O(n) time. In contrast, binary search performs better on sorted arrays and guarantees O(log n). Therefore, binary search is recommended for large datasets.

Conclusion

Through this problem, we learned how to find integers in an array using Swift. We understood how to solve the problem using basic linear search and also learned about improving performance with more efficient binary search. We encourage you to develop your skills in solving algorithm problems through continuous practice.