Search an Element in an Array : Program CPP Java

Problem Statement: Search an element in an array and return its position

Examples:

Example 1:
Input: array[] = {1,2,3,4,5} k=3                                                                              Output: 2                                                                                                              Explanation: The answer is 2 because 3 is present at 2nd index.

Example 2:
Input: array[]={6,7,9,5,3,10} k=10
Output: 5
Explanation: The answer is 5 because 10 is present at 5th index.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Linear Search

Intuition: Simply traverse through the array and check if k matches the element of the array, if it matches return the index of that element.

Approach:

Traverse through the array.
If arr[i] matches k then return i.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n = 6;
	int arr[n] = {6, 7, 9, 5, 3, 10};
	int k = 10;
	int ans = -1;
	for (int i = 0; i < n; i++) {
		if (arr[i] == k) {
			ans = i;
			break;
		}
	}
	cout <<"The element is present in " <<ans<<" index";
}

Output: The element is present in 5 index

Time Complexity: O(n)

Space Complexity: O(1).

Java Code

public class Main {
  public static void main(String args[]) {
    int arr[] = {6,7,9,5,3,10};
    int n = arr.length;
    int k = 10;
    int ans = -1;
    for (int i = 0; i < n; i++) {
      if (arr[i] == k) {
        ans = i;
        break;
      }
    }
    System.out.print("The element is present in "+ans+" index");
  }
}

Output: The element is present in 5 index

Time Complexity: O(n)

Space Complexity: O(1).

Solution 2: Optimized solution(provided the array is sorted)

Intuition: If the array is already sorted we can find the index of the element in O(logn).

Approach:

Use the binary search algorithm.
Maintain two variables low and high.Initially low is 0 and high is n-1.low to high is the range of the index where the elements can possibly lie.
Take another variable mid.mid = (low+high)/2.
If the element at mid is less than k,then the required index should obviously be between mid+1 to r,so make l=mid+1.
If the element at mid is greater than k,then the required index should obviously be between l to mid-1,so make r=mid-1.
If the element at mid is equal to k then return mid.
This way we go on reducing the range.If at some point r>l then the element is not present in the array.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n = 6;
	int arr[n] = {6, 7, 9, 5, 3, 10};
	int k = 10;
	int low = 0, high = n - 1;
	int ans = -1;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (arr[mid] > k) {
			high = mid - 1;
		}
		else if (arr[mid] < k) {
			low = mid + 1;
		}
		else {
			ans = mid;
			break;
		}
	}
	cout << "The element is present in "<<ans<<" index";
}

Output: The element is present in 5 index

Time Complexity: O(logn).

Space Complexity: O(1)

Java Code

public class Main {
  public static void main(String args[]) {
    int arr[] = {6,7,9,5,3,10};
    int n = arr.length;
    int k = 10;
    int low = 0, high = n - 1;
    int ans = -1;
    while (low <= high) {
      int mid = (low + high) / 2;
      if (arr[mid] > k) {
        high = mid - 1;
      } else if (arr[mid] < k) {
        low = mid + 1;
      } else {
        ans = mid;
        break;
      }
    }
    System.out.print("The element is present in "+ans+" index");
  }
}

Output: The element is present in 5 index

Time Complexity: O(logn).

Space Complexity: O(1)

Special thanks to Pranav Padawe for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article