### Remove duplicates in a sorted integer array sortedarray array searching remove timecomplexity    Posted: 5 years ago Updated: 4 years ago Edit answers (1) views (4030)

Can you improve the time complexity in Remove duplicates in an integer array if the input array is sorted?

 Posted: 5 years ago Updated: 5 years ago 0 0 Edit We can improve the time complexity to find the duplicates in an array when the input array is sorted. Let us assume that the numbers are increasing by $$1$$ and starting from $$0$$. We can use modified binary search to find the duplicates. Find the middle element of the input array and compare it with its index. If they are same, the duplicate element(s) will be at the upper half of the array. Otherwise, it will be at the lower half of the array. Time complexity = $$O(logn)$$.public static int findDuplicates(int[] array) { int low = 0; int high = array.length - 1; while (low < = high) { int middle = (low + high); int middleValue = array[middle]; if (middleValue == middle) low = middle + 1; else high = middle - 1; } return high; }