Search an Element (Linear & Binary)

Introduction

In the previous chapters, you learned how to construct an array and how to get an element using an index.

However, in most cases, we need to look up or search for a specific element in the array or other data structures. This is the most common use case for a developer when customizing or building a software product.

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

How many ways do you know to search for an element in an array? Consider this and develop some thought processes before looking for the following algorithms.

In this lesson, we will see two ways to solve this problem.

1. Linear search
2. Binary search

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.

Linear search

The linear search algorithm is a 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
      }
    }
    return -1; // return -1 if the element is not 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 {
      System.out.println("Element not found");
    }
  }
}

/* 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

1. 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).
2. 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.

Binary search

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:

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
      }
    }

    return -1; // return -1 if the element is not found
  }

  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 {
      System.out.println("Element not found");
    }
  }
}

/* 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

1. 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.
2. 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.