Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Missing Number in Sorted Array

Explore how to find the missing number in a sorted array by comparing a naive linear search approach with a more efficient divide and conquer method. Understand both solutions’ logic and time complexities to apply the optimal algorithm for coding interviews.

We'll cover the following...

Solution # 1

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

C++
int missingNumber(int arr[], int N) { 
	int missing = -1;
  int last = arr[0];
  for(int i=1;i<N;i++){
    if(arr[i] != last + 1) {
       missing = last + 1;
       break;
    }
    last++;
  }
  return missing;
}

  • (Line 2): Initialize missing equal to
...