Index Of an Extra Element Geeks solution

Index Of an Extra Element Geeks solution

  July 23, 2017    

---

Problem :

Given two sorted arrays. There is a difference between the arrays. First array has one element extra added in between. Find the index of the extra element.

Idea is to use binary search so that we can solve it in O(log n) time 

n is length of biggest array

Code:

public int findExtra(int a[],int b[],int n)
        {
         int index=n-1;
         int i=0,j=n-2;
         while(i<=j)
         {
             int mid=(i+j)/2;
             if(a[mid]!=b[mid])
             {
                 index=mid;
                 j=mid-1;
             }
             else
             {
                 i=mid+1;
             }
         }
         return index;
        }