Find the Index of An Array Element in Java
In the input an integer array of size N and an integer value K is given to us. The task is to return the index of the element that is equal to K in the array in Java. If the integer is not available in the array, then return -1.
Example 1:
Input: Arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, K = 9
Output: 8
Explanation: The integer value '9' is stored in the 8th index of the array.
Example 2:
Input: Arr[] = { 5, 3, 7, 1, 4, 8, 10, 15, 11, 2, 6}, K = 10
Output: 6
Explanation: The integer value '10' is stored in the 6th index of the array, so return 6.
Example 3:
Input: Arr[] = { 5, 3, 7, 1, 4, 8, 10, 15, 11, 2, 16}, K = 9
Output: -1
Explanation: The integer value '9' is not available in the array, so return -1.
Example 4:
Input: Arr[] = { 1, 1, 1, 1, 2, 2, 2, 3, 3, 3}, K = 1
Output: 0
Explanation: The integer value '1' is stored in the 0th index of the array, so return 0.
Approach 1: Using Linear Search
A specific value can be easily located from an array using the algorithm of linear search. Also, the time complexity of the algorithm is O(N) when linear search is implemented. You can find the implementation of the above-mentioned problem statement using a linear search below:
Filename: FindIndex.java
import java.util.*; public class FindIndex { // Function which implements linear search algorithm and returns the required // index of the integer from the array. public static int findIndexArray(int Arr[], int K) { // If the size of the array is 0 or null. if (Arr == null) { return -1; } // Calculates the length of the array. int L = Arr.length; int I = 0; // Traverses the array while (I < L) { // Returns the index if the element is available in the array; else returns -1. if (Arr[I] == K) { return I; } else { I = I + 1; } } return -1; } public static void main(String[] args) { int[] Arr = { 5, 3, 7, 1, 4, 8, 10, 15, 11, 2, 6}; int K = 10; //Calculates and prints the index of integer value K System.out.println("The index position of integer value "+K+" is: " + findIndexArray(Arr,K)); } }
Output
The index position of integer value 10 is: 6
Complexity Analysis
The time complexity of the above-mentioned linear search implementation is O(N), whereas the space complexity is O(1).
Approach 2: Using ArrayList
Step 1: Store all the elements or values of the array in an ArrayList.
Step 2: Use the indexOf() method of ArrayList to find the index of the specific Kth element.
Step 3: Print the value returned from the indexOf() method.
Step 4: If the element is not available in the array, -1 will be returned.
Step 5: Else, the index of the element will be returned.
Filename: FindIndex1.java
import java.util.ArrayList; public class FindIndex1{ public static int findIndex(int Arr[], int K) { ArrayList<Integer> list = new ArrayList<>(); // Adds the elements of an array into the arraylist. for (int i : Arr) list.add(i); //Returns the index of the element to be found. return list.indexOf(K); } public static void main(String[] args) { int[] Arr = { 5, 3, 7, 1, 4, 8, 10, 15, 11, 2, 6 }; int K = 10; System.out.println("The index position of integer value "+K+": " + findIndex(Arr, K)); } }
Output
The index position of integer value 10 is: 6
Complexity Analysis
The time complexity of the above-mentioned ArrayList approach is O(N), whereas the space complexity is O(N).
Approach 3: Using Binary Search
Binary search is one of the most used algorithms for searching an element in arrays. However, the binary search algorithm can only be applied to arrays that are sorted (ascending or descending order).
In Java, an inbuilt function is provided in the library of Arrays, which returns the index of the specific element from the array. The complexity of the above-mentioned method will be O(log N).
Step 1: Create a recursive binary search method that returns the index of the specified element using concepts of binary search.
Step 2: Pass the array and the target element into the binary search method.
Step 3: Print the index value returned by the binary search method. If the element is not available in the array, then the binary search returns -1. Otherwise, it returns the index of the element in the array.
Filename: FindIndex2.java
import java.util.Arrays; public class FindIndex2 { // Function that returns the index of the element or value to be found. public static int findIndexArrat(int Arr[], int K) { int FindIndex = Arrays.binarySearch(Arr, K); return (FindIndex < 0) ? -1 : FindIndex; } public static void main(String[] args) { int[] Arr = { 1, 2, 3, 4, 5, 6 }; int K = 1; // Prints the index of the Kth value element in the array. int ans = findIndexArrat(Arr, K); if (ans == -1) System.out.println("The required integer value is not available in the input array"); else System.out.println("The index position of integer value " + K + " = " + findIndexArrat(Arr, K)); } }
Output
The index position of integer value 1 = 6
Complexity Analysis
The time complexity of the above-mentioned Binary Search approach is O(logN), whereas the space complexity is O(1).
Approach 4: Using Recursion
The index of the specified value from an array will be calculated using a recursive function. If the specified target element is available in the array, its index will be returned; -1 will be returned.
Filename: FindIndex3.java
import java.util.*; public class FindIndex3{ public static int findIndexArray(int Arr[], int K, int S) { // If the values of S and the length of the array are equal, return -1. (Base Condition) if (S == Arr.length) return -1; //If the value of the array's Sth element equals K, return S. if (Arr[S] == K) return S; return findIndexArray(Arr, K, S + 1); } public static int findIndex(int Arr[], int K) { return findIndexArray(Arr, K, 0); } public static void main(String[] args) { int[] Arr = { 5, 3, 7, 1, 4, 8, 10, 15, 11, 2, 6 }; int K = 10; System.out.println("The index position of integer value "+K+" " + (Arr, K); } }
Output
The index position of integer value 10 is: 6
Complexity Analysis
The time complexity of the above-mentioned Binary Search approach is O(N), whereas the space complexity is O(1).
Approach 5: Using Stream API
From the Java 8 version, Stream is introduced as a new abstract layer. The data can be processed in a declarative manner using Stream API.
A method called IntStream is provided by the Stream package, which is used for finding the index of a specific element from an array. The IntStream of all the elements from 0 to N-1 indices will be calculated, where n represents the length of the array.
Filename: FindIndex4.java
import java.util.stream.IntStream; public class FindIndex4 { // Function that returns the index of the specific element from Array using // IntStream method. public static int findIndexArray(int Arr[], int K) { int L = Arr.length; return IntStream.range(0, L) .filter(i -> K == Arr[i]) .findFirst() //Finds the first occurrence of the element. .orElse(-1); // If No element is found } public static void main(String[] args) { int[] Arr = { 5, 3, 7, 1, 4, 8, 10, 15, 11, 2, 6 }; int K = 10; System.out.println("The index position of integer value "+K+" is: " + findIndexArray(Arr, K)); } }
Output
The index position of integer value 10 is: 6
Complexity Analysis
The time complexity of the above-mentioned Binary Search approach is O(N), whereas the space complexity is O(1).
Approach 6: Using Guava
Guava can be determined as an open-source, Java-based library that was developed by Google. Various utility methods are provided by Guava related to caching, concurrency, string processing, etc.
indexOf() method is available in the Guava library, which is used to return the index of the first occurrence of a specified element from an array.
Filename: FindIndex5.java
import java.util.List; import com.google.common.primitives.Ints; public class FindIndex5 { //Function that returns the index of the first occurrence of an element from the array. public static int findIndexArray(int Arr[], int K) { return Ints.indexOf(Arr, K); } public static void main(String[] args) { int[] Arr = { 5, 3, 7, 1, 4, 8, 10, 15, 11, 2, 6 }; int K = 10; System.out.println("The index position of integer value "+K+" " + findIndexArray(Arr, K)); } }
Output
The index position of integer value 10 is: 6
Complexity Analysis
The time complexity of the above-mentioned Binary Search approach is O(N), whereas the space complexity is O(1).