This is a problem to check the existence of a specific integer 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.<\/p>\n 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).<\/p>\n Let’s implement the code using the binary search method described above. Below is the code written in C#.<\/p>\n 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.<\/p>\nx<\/code> in a given integer array arr<\/code>. If the integer x<\/code> exists in the array, it should return true<\/code>, and if it does not exist, it should return false<\/code>.<\/p>\nInput Format<\/h3>\n
\n
arr<\/code> (1 \u2264 arr.Length<\/code> \u2264 100,000)<\/li>\nx<\/code> (-1,000,000 \u2264 x<\/code> \u2264 1,000,000)<\/li>\n<\/ul>\nOutput Format<\/h3>\n
\n
x<\/code> exists in the array, it should return true<\/code>, otherwise false<\/code>.<\/li>\n<\/ul>\nExample Input and Output<\/h3>\n
Input: arr = [1, 2, 3, 4, 5], x = 3\nOutput: true\n\nInput: arr = [1, 2, 3, 4, 5], x = 6\nOutput: false<\/code><\/pre>\n<\/section>\nApproach to the Problem<\/h2>\n
Efficient Approach<\/h3>\n
Possible Methods<\/h3>\n
\n
Code Implementation<\/h2>\n
using System;\n\nclass Program\n{\n static void Main()\n {\n int[] arr = { 1, 2, 3, 4, 5 };\n int x = 3;\n bool result = Contains(arr, x);\n Console.WriteLine(result); \/\/ true\n \n x = 6;\n result = Contains(arr, x);\n Console.WriteLine(result); \/\/ false\n }\n\n static bool Contains(int[] arr, int x)\n {\n int left = 0;\n int right = arr.Length - 1;\n\n while (left <= right)\n {\n int mid = left + (right - left) \/ 2;\n\n \/\/ Return true if x equals the mid value\n if (arr[mid] == x)\n return true;\n \/\/ Search the left half if x is smaller than the mid value\n else if (arr[mid] > x)\n right = mid - 1;\n \/\/ Search the right half if x is larger than the mid value\n else\n left = mid + 1;\n }\n\n return false; \/\/ x does not exist in the array\n }\n}<\/code><\/pre>\n<\/section>\nComplexity Analysis<\/h2>\n
Time Complexity<\/h3>\n
Space Complexity<\/h3>\n