...

/

Solution: Missing Number in a Sorted Array

Solution: Missing Number in a Sorted Array

Review various solution approaches to find the missing number in a sorted array in detail.

Solution 1

A naive solution to this problem is traversing through the whole array, starting from the first index and returning the missing integer as soon as we encounter it.

using System;
public class Program
{
/// <summary>
/// Finds a missing number from an array that contains sorted numbers starting from 1.
/// </summary>
/// <param name="arr">Array of sorted integers.</param>
/// <returns>The missing number in the sorted array.</returns>
public static int MissingNumber(int[] arr)
{
int actualNumber = 1; // Grows in ascending order
foreach (int i in arr) // Iterating the entire array
{
if (i != actualNumber) // If the number in the array is not equal to actual number
{
return actualNumber; // This is the missing number in the array
}
actualNumber = actualNumber + 1; // Incrementing the actual number by 1
}
return -1; // If there is no missing number
}
// Driver code to test above method
public static void Main(string[] args)
{
Console.WriteLine(MissingNumber(new int[] { 1, 2, 4 }));
Console.WriteLine(MissingNumber(new int[] { 1, 2, 3, 4, 6 }));
Console.WriteLine(MissingNumber(new int[] { 2, 3, 4, 5, 6 }));
Console.WriteLine(MissingNumber(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }));
}
}

Explanation

  • Line 12: actualNumber is initialized with 1 because the list is supposed to start with 1.
  • Line 16: We compare each element of the list with actualNumber.
  • Line 18: If any number in the list doesn’t match with
...