Find the duplicate number from unsorted array

There are many methods to find out the duplicate numbers form the array. We can use the map which will store the values from the array as a key, while storing itself we can check for duplicate insertion. If map.insert flags out duplicate insertion that means we found out duplicate.
Code below uses the same technique to find the duplicate.

typefec vector<int> IntVect; void PrintDuplicateNumberFromUnsortedArrayWithMap(IntVect & A) {     std::map<int, int> mapOfInt;     std::pair<std::map<int, int>::iterator, bool> retVal;     for (int  i = 0; i < A.size(); i++)     {         retVal = mapOfInt.insert(make_pair(A[i], i));         if (retVal.second == false)         {             cout << "Found Duplicate for : " <<  A[i] << "  at : " << retVal.first->second  << endl;         }     } }

The above method is faster way to find the duplicate but it requires the storage.

If we want to avoid the temporary storage then we can just sort the array then find the duplicate by comparing the consecutive elements just in one pass as given in code below.

void FindDuplicateWithSorting(IntVect & vect) {     if (vect.size() > 0)     {         // Sort vector using any standard sort like quick sort         int prev = vect[0];         for (size_t i = 1; i < vect.size(); i++)         {             if (prev == vect[i])             {                 cout << "Duplicate exists for the number : " << prev << endl;             }             prev = vect[i];         }     } }

This code will have the time complexity equal to the time complexity of the sorting algorithm used for sorting the array because after sorting we will be using just one pass to search the duplicate.

Searching number in sorted but rotated array

Consider a sorted array as below 

15  19  29  34  35  49   96  97 99

the rotated sorted array of this array can be 

49 96  97 99  15  19  29  34  35  

Approach 1:
We have to find the element from this array. With linear search we can find the element in o(n) time complexity. But as array is sorted we should take advantage of this property.
Approach 2:
We can use the binary search for searching the PIVOT element. Pivot element will denote the starting point of rotation.  You can check the Binary search is implementation here.
With this we will minimize the search area and then apply the binary search again on the remaining array.

Approach 3:
With above approach we will be doing two pass of binary search one for searching pivot and one for searching the number. We can even think of modifying the binary search as we know if the array is rotate. 
Code below shows how we can use modified binary search method to find element in sorted but rotated array.
   

//Num is number to search int SearchNum(vector<int> & input, int start, int end, const int num) {     if (start <= end)     {         int mid = start + (end - start) / 2;         if (num == input[mid])             return mid;         if (input[mid] < input[end])         {             if (input[mid] < num && input[end] >= num)                 return SearchNum(input, mid + 1, end, num);             else                 return SearchNum(input, start, mid - 1, num);         }         else         {             if (input[start] <= num && input[mid] > num)                 return SearchNum(input, start, mid - 1, num);             else                 return SearchNum(input, mid + 1, end, num);         }     }     return -1; }

The function will return -1 if it failed to find the number else it will return index of the number in the array.

Implementing Binary Search Algorithm in C++/C

BinarySearch method implements binary search algorithm. This method you can use in C/C++ program. Method takes integer array, array start position, array last element position, and value to search as input. Method returns position of the value to search in the array, if value not found then it returns -1. As we know binary search algorithm can only be used for sorted arrays. In case if you wish to use binary search on an array which is not sorted then you must sort it using some sorting technique and then use binary search algorithm to find the desired element in the array. 

int BinarySearch( int * intArray, int start, int end, int key) {     while( start <= end )     {         int mid = (start + end)/2;            if( intArray[mid] == key)             return mid;         if( key < intArray[mid]  )             end = mid - 1;         else             start = mid + 1;     }     return -1; }

Binary search can also be implemented in recursive way as below. 

int RecBinarySearch( int * intArray, int start, int end, int key) {     if( start <= end )     {         int mid = (start + end)/2;            if( intArray[mid] == key)         {             return mid;         }         else         {             if( key < intArray[mid]  )                 return    RecBinarySearch( intArray, start, mid-1, key);             else                 return RecBinarySearch( intArray, mid+1, end, key);         }     }     else         return -1; // Element not Found }