702734. Searching in an Array
Searching in an Array
Slug: searching-a-number0324
Difficulty: Basic
Id: 702734
Topic Tags: Arrays, Searching, Data Structures, Algorithms
Company Tags: None
Summary
Searching for a specific element in an array is a fundamental problem in computer science. This problem involves iterating through the array to find a target value. The key concept involved is searching.
Detailed Explanation
The algorithmic approach to this problem is to iterate through the array and compare each element with the target value. If the element matches the target, then it's found; if not, continue until the end of the array or the target is found.
Here's a step-by-step breakdown of the solution:
- Initialize two pointers:
lowat the start of the array (arr[0]) andhighat the end of the array (arr[arr.length - 1]). - Calculate the midpoint using the formula
(low + high) / 2. - Compare the value at the midpoint with the target.
- If the values match, return the midpoint index.
- If the target is less than the midpoint's value, update
highto the midpoint - 1 and repeat from step 2. - If the target is greater than the midpoint's value, update
lowto the midpoint + 1 and repeat from step 2.
The time complexity for this algorithm is O(log n), where n is the size of the array. This is because we're effectively dividing the search space in half at each iteration. The space complexity is O(1), as we only use a constant amount of space to store the pointers and other variables.
Optimized Solutions
Java
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if (target < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1; // not found
}