701217. Array Search
Array Search
Slug: search-an-element-in-an-array-1587115621 Difficulty: Basic Id: 701217 Topic Tags: Arrays, Searching, Data Structures, Algorithms Company Tags: None
Summary
Given an array of integers and a target integer, the problem is to find if the target integer exists in the array. This is a basic searching problem that involves iterating through the array and comparing elements until the target element is found or it's determined that the element is not present.
Detailed Explanation
The algorithmic approach for this problem is to iterate through the array and compare each element with the target element. If the target element is found, return true; otherwise, return false after iterating through the entire array.
Here's a step-by-step breakdown of the solution:
- Initialize two pointers,
startandend, to represent the start and end indices of the array. - Calculate the midpoint index
midusing the formula(start + end) / 2. - Compare the element at the
midindex with the target element. - If the elements match, return true (the target element is found).
- If the elements don't match, update the
startorendpointer based on whether the target element could be in the left or right half of the array. - Repeat steps 2-5 until the target element is found or the search space has been exhausted (i.e.,
start >= end).
Time complexity: O(log n), where n is the length of the array, since we're effectively performing a binary search. Space complexity: O(1), as we only need to keep track of three indices.
Optimized Solutions
Java
public boolean search(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == target) {
return true;
}
if (arr[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return false;
}