Finding the missing number using binary search
Description :
/**
* Find missing number in a sequence Minimum complexity (n Log n)
*
* input : {1,2,3,5}
* output : 4
*/
package com.steffi.solutions;
import java.util.Arrays;
/**
* @author Consumerfed Information Technology Section
*
*/
public class MissingNumberArray {
private static int loopCount = 0;
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
int[] a = {1,2,3,4,6,7,8,9,10,11,12};
int len = a.length;
MissingNumberArray m = new MissingNumberArray();
int value = 0;
if(a[len-1]!=len) {
value = m.findMissingNumber(a, 0, len);
System.out.println(" The Missing number in the array :"+Arrays.toString(a)+" is "+value);
}else {
loopCount++;
System.out.println(" There is no missing number in the given array "+Arrays.toString(a));
}
System.out.println(" For "+len+" size array it tooks "+loopCount+" search to find the answer ");
System.out.println(" Complexity :"+len*Math.log(len));
System.out.println(" Time Taken : "+(System.currentTimeMillis() - startTime)+" ms");
}
private int findMissingNumber(int[] array, int startPstn, int endPstn) {
loopCount++;
int arraySize = endPstn - startPstn;
int position = startPstn + arraySize / 2;
if(arraySize==0) {
return position +1;
}else if (arraySize == 1) {
return array[position] + 1;
}
else if (array[position] != position + 1) {
return findMissingNumber(array, startPstn, position);
} else {
return findMissingNumber(array, position + 1, endPstn);
}
}
}
Output
The Missing number in the array :[1, 2, 3, 5] is 4
For 4 size array it tooks 2 search to find the answer
Complexity :5.545177444479562
Time Taken : 4 ms
The Missing number in the array :[1, 2, 3, 5, 6, 7, 8, 9, 10] is 4
For 9 size array it tooks 3 search to find the answer
Complexity :19.775021196025975
Time Taken : 4 ms
The Missing number in the array :[1, 2, 3, 4, 5, 6, 7, 8, 10] is 9
For 9 size array it tooks 3 search to find the answer
Complexity :19.775021196025975
Time Taken : 3 ms
The Missing number in the array :[1, 2, 3, 4, 5, 6, 7, 8, 9, 11] is 10
For 10 size array it tooks 3 search to find the answer
Complexity :23.02585092994046
Time Taken : 2 ms
The Missing number in the array :[1, 2, 4, 5] is 3
For 4 size array it tooks 3 search to find the answer
Complexity :5.545177444479562
Time Taken : 3 ms
The Missing number in the array :[1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12] is 4
For 11 size array it tooks 4 search to find the answer
Complexity :26.376848000782076
Time Taken : 3 ms
The Missing number in the array :[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14] is 13
For 13 size array it tooks 4 search to find the answer
Complexity :33.34434164699998
Time Taken : 3 ms
Buy any thing from amazon through us !!!