Find the starting index of a sub-array from the first array

<< Previous

Table of Categories

Next >>

---

 
   /**
    * Please note: even though I just used Integer Array in this task, the algorithm could be
    * used for any Array
   */
 public static int firstIndexOfSubArray(int[] arr1, int[] arr2) 
 {
        if (arr1 == null || arr2 == null) 
       {
            return -1;
        }
        int len1 = arr1.length;
        int len2 = arr2.length;
        if (len1 == 0 || len2 == 0 || len1 < len2) 
       {
            return -1;
       }
        //start the sliding window from the left side
        int slidingFrom = 0;
        int i = slidingFrom;
        int j = 0;
        int firstEqualIndex = -1;
        while (true) 
       {
            //if the sliding window is out of boundary,just return
            if (len2 > (len1 - slidingFrom)) 
           {
                return -1;
            }
            //find the first equal element
            if (firstEqualIndex == -1) 
            {
                if (arr1[i] == arr2[0]) 
               {
                    firstEqualIndex = i;
                    slidingFrom = i;
                    j = 1;
                }
                i++;
                continue;
            }
            //if already found the first equal element, compare the following elements
            if (arr1[i] == arr2[j]) 
           {
                //if equal, contiue to compare until the last element in array 2
                i++;
                j++;
                if (j == len2) 
                {
                    break;
                }
            } 
          //if not equal, slide to the next one and compare every element in array 2 again
            else
            {
                firstEqualIndex = -1;
                i = slidingFrom + 1;
            }
         }
         return firstEqualIndex;
  }