mardi 24 mars 2020

How the condition in "if statement" can give the section of array in which the repeated elements lie?

Given an array a[] of N positive integers, where elements are consecutive (sorted). Also, there is a single element which is repeating X (any variable) number of times. Now, the task is to find the element which is repeated.

while (start < end) 
        { 
            int mid = (start + end) / 2; 

            // if a[mid] >= mid + a[0], there is no repeating character in [start,mid]
            if (a[mid] >= mid + a[0]) 
                start = mid + 1; 

           // if a[mid] < mid + a[0], there is a repeating character in [start,mid]
            else
                end = mid; 
        }

Aucun commentaire:

Enregistrer un commentaire