Finding Duplicates in a Sorted Array

Finding duplicates in a sorted array is a common operation in computer science. Because the array is sorted, duplicate elements will be adjacent to each other. This makes the task easier compared to an unsorted array. One can use a single loop to traverse the array, comparing adjacent elements to find duplicates.

Example Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public class Main {
  public static void main(String[] args) {
    int[] array = {1, 2, 2, 3, 4, 4, 5};

    for (int i = 0; i < array.length - 1; i++) {
      if (array[i] == array[i + 1]) {
        System.out.println("Duplicate found: " + array[i]);
      }
    }
  }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <iostream>
using namespace std;

int main() {
  int array[] = {1, 2, 2, 3, 4, 4, 5};
  int length = sizeof(array) / sizeof(array[0]);
  
  for (int i = 0; i < length - 1; i++) {
    if (array[i] == array[i + 1]) {
      cout << "Duplicate found: " << array[i] << endl;
    }
  }
  
  return 0;
}

Python

1
2
3
4
5
array = [1, 2, 2, 3, 4, 4, 5]

for i in range(len(array) - 1):
    if array[i] == array[i + 1]:
        print(f"Duplicate found: {array[i]}")

Key Takeaways

A sorted array allows for simpler and more efficient algorithms.
A single loop can be used to compare adjacent elements.
If adjacent elements are equal, a duplicate is found.