Today's coding problem is not very new, it's age old classic from programming interviews. You have a sorted array containing n - 1 unique numbers starting from 0 to n - 1. There is only one number missing in this range and you need to find that out. I mean you need to write a Java method to find the missing number and print it's value in the console. Some of you might have seen this question before, but if you have not been asked this question before, what is the first approach comes into your mind to solve this question? Since only one number is missing, many programmers come up with the approach of iterating over the array and comparing each element with the expected one e.g. first element should be 0, the second element should be 1 and so on. Though this will sort the problem, it will costs you

O(n) time. What can you do to improve performance? The key here has we have sorted the array, do you think our earlier solution is taking full advantage of this knowledge, well it is but not fully. What it is doing is performing linear search which is costing

O(n), but if you do binary search, which of course need a sorted array, we can reduce the time taken in the range of

O(logN). Since numbers are in the range from 0 to n - 1 and are sorted, the first number till the missing one should be same as their indexes. I mean if 0 is not missing, then it must be in the first index i.e. at 0. If you generalize this, you will find out that if the missing number is k then all numbers less than k are located in an array with indexes same as their value. Also number k + 1 will be located at index k, and number k + 2 will be located at index k + 1. What does this mean? Well, it means that missing number is the first cell whose value is not same as its index. So our problem reduces to

search in an array to find the first cell, whose value is not same as its index. You can easily find out this by using binary search algorithm in

O(logN) time. Our function implements this logic to find the missing integer in a sorted array in Java. You can use this solution to find missing number in array of numbers 1-1000 or 1 -100.