Given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer.

Tha basic method that comes in mind is to iterate from 1 to n and compare the values within the list. This will solve the problem, it will cost you O(n) time. The time complexity of your solution would be O(n) which is not good for a big array, like with 100 million entries. **What can you do to improve performance?**

An **efficient solution** is based on the divide and conquer algorithm that we have seen in binary search. This solution has a time complexity of O(log n) .

package main import ( "errors" "fmt" ) func main() { values := []int{0, 1, 2, 3, 4, 5, 7, 8} missingNumber, err := findMissingNumber(values) if err != nil { fmt.Println(err) } else { fmt.Println(missingNumber) } } func findMissingNumber(numbers []int) (int, error) { if len(numbers) <= 0 { return 0, errors.New("Null or Empty array not permitted") } left := 0 right := len(numbers) - 1 for left <= right { middle := (right + left) >> 1 if numbers[middle] != middle { if middle == 0 || numbers[middle-1] == middle-1 { return middle, nil } right = middle - 1 } else { left = middle + 1 } } return 0, errors.New("No missing number") }