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