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

**Examples:**

Example 1:Input:array[] = {1,2,3,4,5} k=3Output:2Explanation:The answer is 2 because 3 is present at 2nd index.Example 2:Input:array[]={6,7,9,5,3,10} k=10Output: 5Explanation: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