# 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.

Data Structures and Algorithms

Gopi is a highly experienced Full Stack developer with a deep understanding of Java, Microservices, and React. He worked in India & Europe for startups, the EU government, and tech giants.

Members Public

## What is Big-O Complexity Analysis

In this lesson, you will gain knowledge about algorithm complexity analysis and the various types of big-O complexity analysis.

Members Public

## Understanding the Importance of Big-O Notation in Coding Interviews

In this lesson, we will introduce the concept of big-o notation, a mathematical tool used to measure algorithm efficiency.

Members Public

## What Are Data Structures And Algorithms?

In this lesson, you will gain knowledge about the significance and correlation between data structures and algorithms.