Tìm phần tử lặp duy nhất trong mảng đã sắp xếp bằng C++

Mô tả bài toán

Cho mảng đã sắp xếp kích thước N chứa 1..N-1, một số lặp hai lần. Tìm số đó.

Ví dụ

arr={1,2,3,4,5,5,6,7} → Output: 5.

Giải thuật

• Duyệt tuyến tính O(N): So sánh arr[i] và arr[i+1].
• Tìm kiếm nhị phân O(log N): So sánh arr[mid] với mid+1. Nếu arr[mid] != mid+1 → lặp ở bên trái hoặc tại mid; else bên phải.

Mã nguồn C++ (Binary Search)

#include <bits/stdc++.h>
using namespace std;

int findRepeatingValueArr(int arr[], int s, int e) {
    if (s > e) return -1;
    int mid = (s+e)/2;
    if (arr[mid] != mid+1) {
        if (mid>0 && arr[mid]==arr[mid-1]) return arr[mid];
        return findRepeatingValueArr(arr, s, mid-1);
    }
    return findRepeatingValueArr(arr, mid+1, e);
}

int main() {
    int arr[] = {1,2,3,4,5,6,6,7,8,9};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Repeating value: " << findRepeatingValueArr(arr,0,n-1);
    return 0;
}

Đầu ra

The repeating value in the array is 6