How To Search For An Element In An Array?

In this lesson, you will learn two popular searching algorithms developers use all the time to search for an element in an array.

Introduction

In the previous lesson (how to implement array-like data structure), you learned how to get an element using an `index`.

But, in most cases, we need to lookup or search for a specific element in the array or other data structures. A developer's most common use case when customizing or building a software product is this.

The language APIs provide some of the methods to achieve it. In theory, they are writing an algorithm that we are going to discuss here.

How many ways do you know to search for an element in an array? Think about this and come up with some thought processes before looking for the following algorithms.

In this lesson, we are going to see two different ways to solve this problem.

1. Linear search
2. Binary search

The linear search algorithm is a simple and straightforward method for finding a specific element within an array.

It works by sequentially checking each element in the array until a match is found or the end of the array is reached.

Here's an example of a linear search algorithm implemented in Java.

Code

Given an unsorted array of distinct integers `nums` and a `target` value, return the `index` if the `target` is found. If not, return `-1`.

``````public class LinearSearch {
public static int linearSearch(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i; // return the index if the element is found
}
}
}

public static void main(String[] args) {
int[] nums = {5, 2, 9, 1, 7, 4};
int target = 7;

int index = linearSearch(nums, target);
if (index != -1) {
System.out.println("Element " + target + " found at index " + index);
} else {
}
}
}

/* Outputs: Element 7 found at index 4 */``````

Explanation

The `linearSearch` method takes an integer array `nums` and a target element `target` as parameters.

It iterates through each element of the array using a `for` loop and compares it with the `target` element. If a match is found, it returns the `index` of the target element. If the end of the array is reached without finding a match, it returns -1 to indicate that the element is not present.

The `main` method demonstrates the usage of the `linearSearch` method by initializing an array and performing a linear search for the target element. The result is then printed based on whether the element was found or not.

Complexity analysis

Time complexity: `O(n)`

If `n` is the number of elements present in the array, our algorithms run through each element to check for the match. The overall time complexity is `O(n)`.

Space complexity: `O(1)`

The space complexity is `O(1)` since no additional space is allocated, the space required does not depend on the size of the input array, so only constant space is used.

The binary search algorithm is an efficient method for finding a specific element within a sorted array. It works by repeatedly dividing the search space in half until the target element is found or it is determined that the element does not exist in the array.

Note: Binary search is efficient only if we are dealing with sorted integers. If not, we first need to sort the entire array that takes `O(nlogn)` time and then we need to apply the binary search algorithm.

Here's an example of a binary search algorithm implemented in Java:

Problem statement

Given an array of integers `nums` which is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`. If `target` exists, then return its index. Otherwise, return `-1`.

Algorithm

1. Initialize the boundaries of the search space as `startIndex = 0` and `int endIndex = nums.length - 1`.
2. If there are elements in the range `[startIndex, endIndex]`, we find the middle index `int middleIndex = (startIndex + endIndex) / 2` and compare the middle value `nums[middleIndex]` with `target`:
1. `nums[middleIndex] == target`, return `middleIndex`.
2. If `nums[middleIndex] < target`, let `startIndex = middleIndex + 1` and repeat step 2.
3. If `nums[middleIndex] > target`, let `endIndex = middleIndex - 1` and repeat step 2.
3. We finish the loop without finding `target` element, return `-1`.

Code

``````public class BinarySearch {
public static int binarySearch(int[] nums, int target) {
int startIndex = 0;
int endIndex = nums.length - 1;

while (startIndex <= endIndex) {
int middleIndex = startIndex + (endIndex - startIndex) / 2;

if (nums[middleIndex] == target) {
return middleIndex; // return the index if the element is found
} else if (nums[middleIndex] < target) {
startIndex = middleIndex + 1; // continue searching in the endIndex half
} else {
endIndex = middleIndex - 1; // continue searching in the startIndex half
}
}

}

public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5, 6, 7};
int target = 4;

int index = binarySearch(nums, target);
if (index != -1) {
System.out.println("Element " + target + " found at index " + index);
} else {
}
}
}

/* Outputs: Element 4 found at index 3 */``````

Explanation

The `binarySearch` method takes an integer array `nums` and a target element `target` as parameters.

It maintains two pointers `startIndex` and `endIndex`, which defines the current search space. It repeatedly calculates the `middleIndex` of the search space and compares the element at that index with the `target` element.

If the element at the `middleIndex` is equal to the `target` element, it returns the index. If the element is less than the `target`, the search is continued in the right half of the array by updating the `startIndex` pointer. If the element is greater than the target, the search is continued in the left half by updating the `endIndex` pointer. The process continues until the target element is found or the search space is exhausted.

The `main` method demonstrates the usage of the `binarySearch` method by initializing a sorted array and performing a binary search for the target element. The result is then printed based on whether the element was found or not.

Complexity analysis

Time complexity: `O(logn)`

`nums` is divided into half each time. In the worst-case scenario, we need to cut `nums` until the range has no element, and it takes logarithmic time to reach this break condition.

Space complexity: `O(1)`

During the loop, we only need to record three indexes, `startIndex`, `endIndex`, and `middleIndex`, they take up constant space. Hence, the space complexity is `O(1)` since no additional space is allocated.

Coding Interview QuestionsArraysData Structures and Algorithms

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

Arrays From Zero To Mastery: A Complete Notes For Programmers

This article discusses array data structure with sketches, memory diagrams, array capacity vs. length, strengths & weaknesses, big-O complexities, and more!