Solution: Missing Number in a Sorted Array
Explore solutions to find the missing number in a sorted array using both a naive iteration and an efficient divide-and-conquer method. Understand boundary cases and time complexities ranging from O(n) to O(log n). This lesson helps you implement and analyze these approaches in C#.
We'll cover the following...
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.
Explanation
- Line 12:
actualNumberis initialized with1because 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
actualNumber, then this is the missing number. Therefore, we return it. - Line 23: We return
-1if there is no missing number in the given sorted list