Algorithm | Linear Search

Tags:

Linear Search Algorithm

Linear search is an algorithm that searches for a target value sequentially from the beginning of a list to the end.

  • Advantage: it is the simplest search method, easy to implement, and can be used even with an unsorted list.
  • Disadvantage: it is inefficient when the list to search is long.
package com.devkuma.algorithum.programming.search.linear;

public class LinearSearch {

    void search(int[] nums, int target) {
        int index = -1;
        for(int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                index = i + 1;
                break;
            }
        }
        if (index > 0) {
            System.out.println(target + "은 " + index + "번째 있습니다.");
        } else {
            System.out.println(target + "은 없습니다.");
        }
    }

    public static void main(String[] args) {
        LinearSearch search = new LinearSearch();
        search.search(new int[]{1, 5, 3, 2, 8, 9}, 8);
        search.search(new int[]{1, 5, 3, 2, 8, 9}, 4);
    }
}

Execution result:

8은 5번째 있습니다.
4은 없습니다.

The code below finds the minimum value by updating minValue whenever a value smaller than minValue is found among all elements. The maximum value can be found with the same algorithm.

package com.devkuma.algorithum.programming.search.linear;

public class MinLinearSearch {

    void searchMinimum(int[] nums) {
        int minValue = Integer.MAX_VALUE; // maximum value
        for(int i = 0; i < nums.length; i++) {
            if (nums[i] < minValue) {
                minValue = nums[i];
            }
        }
        System.out.println("최소값은 " + minValue + "입니다.");
    }

    public static void main(String[] args) {
        MinLinearSearch search = new MinLinearSearch();
        search.searchMinimum(new int[]{1, 5, 3, 2, 8, 9});
        search.searchMinimum(new int[]{2, 7, 8, 6, 5, 4});
    }
}

Execution result:

최소값은 1입니다.
최소값은 2입니다.

Now let’s solve a problem using the linear search algorithm.

Problem
Given N integers a(0), a(1), ..., a(N-1) and b(0), b(1), ..., b(N-1), choose one value each from the two sequences, a(i), b(j) [i = 0, 1, ..., N-1, j = 0, 1, ..., N-1], and find the minimum value of their sum among sums greater than or equal to integer R.

Solution

package com.devkuma.algorithum.programming.linearsearch;

public class LinearSearchQuiz1 {

    void minSum(int[] aNums, int[] bNums, int r) {
        int minSum = Integer.MAX_VALUE; // maximum value
        for(int i = 0; i < aNums.length; i++) {
            for(int j = 0; j < bNums.length; j++) {
                int sum = aNums[i] + bNums[j];
                if (sum >= r && minSum > sum) {
                    minSum = sum;
                }
            }
        }
        System.out.println("최소값은 " + minSum + "입니다.");
    }

    public static void main(String[] args) {
        LinearSearchQuiz1 search = new LinearSearchQuiz1();

        int[] aNums =   new int[]{9, 5, 3, 7, 8, 9};
        int[] bNums =   new int[]{3, 9, 5, 8, 3, 5};
        int r = 7;
        search.minSum(aNums, bNums, 7);
    }
}

Execution result:

최소값은 8입니다.

The complexity of the example above is O(N^2).