Solution: Missing Number in a Sorted Array
Review various solution approaches to find the missing number in a sorted array in detail.
We'll cover the following...
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 orderforeach (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 methodpublic 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 with1
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