Array Search Algorithms: Techniques and Examples

Array Search Algorithms
Array search algorithms are essential for finding specific elements in an array.
These algorithms can be categorized based on their approach and efficiency. Let's
explore some of the most common search algorithms:



1. Linear Search
The simplest search algorithm that sequentially checks each element of the array
until the target is found.

 Time Complexity: O(n)O(n)O(n)
 Space Complexity: O(1)O(1)O(1)
 Algorithm:
1. Start from the first element.
2. Compare each element with the target.
3. Return the index if the element matches, or return -1 if not found.
 Python Implementation:

def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1

 JavaScript Implementation:

function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}

, 2. Binary Search
A much faster search algorithm for sorted arrays, which repeatedly divides the
search range in half.

 Time Complexity: O(log⁡n)O(\log n)O(logn)
 Space Complexity: O(1)O(1)O(1) (iterative) or O(log⁡n)O(\log n)O(logn)
(recursive)
 Algorithm:
1. Initialize two pointers, low and high, to the start and end of the
array.
2. Compute the middle index and compare the middle element with the
target.
3. Narrow the search range based on whether the target is smaller or
larger.
4. Repeat until the range is empty or the target is found.
 Python Implementation:

def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1

 JavaScript Implementation:

function binarySearch(arr, target) {
let low = 0, high = arr.length - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) low = mid + 1;