C# Coding Test Course, Finding the Desired Integer

Problem Description

This is a problem to check the existence of a specific integer x in a given integer array arr. If the integer x exists in the array, it should return true, and if it does not exist, it should return false.

Input Format

  • Integer array arr (1 ≤ arr.Length ≤ 100,000)
  • Integer to search for x (-1,000,000 ≤ x ≤ 1,000,000)

Output Format

  • If the integer x exists in the array, it should return true, otherwise false.

Example Input and Output

Input: arr = [1, 2, 3, 4, 5], x = 3
Output: true

Input: arr = [1, 2, 3, 4, 5], x = 6
Output: false

Approach to the Problem

There are several ways to solve this problem. The simplest method is to iterate through the array sequentially to check whether the given integer exists. However, as the size of the array increases, performance may degrade, so it is necessary to use a more efficient algorithm.

Efficient Approach

If the integer array is sorted, a Binary Search algorithm can be used. Binary search operates by dividing the array in half, resulting in an average time complexity of O(log n).

Possible Methods

  1. Linear Search: O(n) – Compare each element of the array one by one.
  2. Binary Search: O(log n) – When the array is sorted.
  3. Using HashSet: O(1) – Ensure fast search times using a hash set.

Code Implementation

Let’s implement the code using the binary search method described above. Below is the code written in C#.

using System;

class Program
{
    static void Main()
    {
        int[] arr = { 1, 2, 3, 4, 5 };
        int x = 3;
        bool result = Contains(arr, x);
        Console.WriteLine(result);  // true
        
        x = 6;
        result = Contains(arr, x);
        Console.WriteLine(result);  // false
    }

    static bool Contains(int[] arr, int x)
    {
        int left = 0;
        int right = arr.Length - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            // Return true if x equals the mid value
            if (arr[mid] == x)
                return true;
            // Search the left half if x is smaller than the mid value
            else if (arr[mid] > x)
                right = mid - 1;
            // Search the right half if x is larger than the mid value
            else
                left = mid + 1;
        }

        return false; // x does not exist in the array
    }
}

Complexity Analysis

Time Complexity

In the case of binary search, it maintains O(log n) efficiency even in the worst case. This is because the search range is halved with each iteration.

Space Complexity

This algorithm has a space complexity of O(1). It is very memory efficient because it does not use any additional data structures.

Conclusion

In this lecture, we covered the problem of finding a desired integer. Depending on the size or characteristics of the array, various algorithms can be used, and it is important to understand the pros and cons of each algorithm. In addition to binary search, utilizing data structures like hash sets can help check for the existence of elements even more quickly. I hope to gain more experience by solving various problems in the future.