[자바기초.029]Searching Algorithms

[자바기초.029]Searching Algorithms

 

1.Search Algorithm

• 컴퓨터는 많은 양의 데이터를 메모리에 저장하고 원하는 데이터를 빠르게 찾아내는 역할을 합니다.
• 그 중에서 데이터를 찾아내는 일을 "탐색(Searching)"이라고 말합니다.
• 가장 대표적인 Searching 방법인 Sequential(Linear) Search와 Binary Search 알고리즘에 대해 알아봅시다.

 

---

 

2.Sequential Search(Linear Search)

• Sequential Search = Linear Search = 순차 탐색
• Sequential Search는 데이터를 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾아내는 알고리즘 입니다.
• Sequential Search는 정렬되지 않은 데이터(unsorted data)에서 원하는 데이터를 찾을 때 사용합니다.
• Sequential Search는 차례차례 하나씩, 한 방향으로 탐색하기때문에 선형 탐색(Linear Search)이라고도 부릅니다.
• 데이터들은 보통 배열(Array)이나 리스트(List)에 저장되어 있고, 원하는 데이터를 발견하게 되면 데이터의 위치값(index)를 리턴하고, 원하는 값이 없다면 최종적으로 -1을 리턴합니다.

 

[예제1-1] 

아래 코드는 배열(Array)을 이용한 Sequential Search 예제 코드입니다. 한 번 실행해 보세요.

public class ArraySearcher
{
 
    /**
     * Finds the index of a value in an array of integers.
     *
     * @param elements an array containing the items to be searched.
     * @param target the item to be found in elements.
     * @return an index of target in elements if found; -1 otherwise.
     */
    public static int sequentialSearch(int[] elements, int target)
    {
        for (int j = 0; j < elements.length; j++)
        {
            if (elements[j] == target)
            {
                return j;
            }
        }
        return -1;
    }
 
    public static void main(String[] args)
    {
        int[] numArray = {3, -2, 9, 38, -23};
        System.out.println("Tests of sequentialSearch");
        System.out.println(sequentialSearch(numArray, 3));    // 0
        System.out.println(sequentialSearch(numArray, 9));    // 2
        System.out.println(sequentialSearch(numArray, -23));// 4
        System.out.println(sequentialSearch(numArray, 99));    //-1
    }
}

 

 

[예제1-2]

아래 코드는 ArrayList를 이용한 Sequential Search 예제 코드입니다. 한 번 실행해 보세요.

import java.util.*;
 
public class ArrayListSearcher
{
 
    /**
     * Finds the index of a value in an ArrayList of integers.
     *
     * @param elements an array containing the items to be searched.
     * @param target the item to be found in elements.
     * @return an index of target in elements if found; -1 otherwise.
     */
    public static int sequentialSearch(ArrayList<Integer> elements, int target)
    {
        for (int j = 0; j < elements.size(); j++)
        {
            if (elements.get(j) == target)
            {
                return j;
            }
        }
        return -1;
    }
 
    public static void main(String[] args)
    {
        ArrayList<Integer> numList = new ArrayList<Integer>();
        numList.add(3);
        numList.add(-2);
        numList.add(9);
        numList.add(38);
        numList.add(-23);
        System.out.println("Tests of sequentialSearch");
        System.out.println(sequentialSearch(numList, 3));    // 0
        System.out.println(sequentialSearch(numList, 9));    // 2
        System.out.println(sequentialSearch(numList, -23));    // 4
        System.out.println(sequentialSearch(numList, 99));    // -1
    }
}

 

• Array를 사용할 때 전체 길이는 length, 요소 하나씩 접근할 때는 [i] 를 사용합니다.
• ArrayList를 사용할 때 전체 길이는 size( ), 요소 하나씩 접근할 때는 get(i) 를 사용합니다.

 

 

[예제1-3]

데이터가 int가 아닌 String일 경우 Sequential Search 코드가 아래에 나와있습니다. 한 번 실행해 보세요.

public class SearchTest
{
 
    public static int sequentialSearch(String[] elements, String target)
    {
        for (int j = 0; j < elements.length; j++)
        {
            if (elements[j].equals(target))
            {
                return j;
            }
        }
        return -1;
    }
 
    public static void main(String[] args)
    {
        String[] arr1 = {"blue", "red", "purple", "green"};
 
        // test when the target is in the array
        int index = sequentialSearch(arr1, "red");
        System.out.println(index);    // 1
 
        // test when the target is not in the array
        index = sequentialSearch(arr1, "pink");
        System.out.println(index);    // -1
    }
}

 

• 데이터가 문자열(String)인 경우에, 문자열끼리 같은지 비교할 때는 equals( ) 를 사용하세요.
• 문자열 끼리 == 로 비교하면 안되고, 만약 == 로 비교하게 되면 두 개의 reference 변수가 같은 String object를 가리키고 있는지 체크하는 거라서 결과가 원하는데로 안나올 수 있습니다.(즉, 두 개의 String object가 같은 문자열이긴 하지만 서로 다른 객체라서 주소값이 달라 다른 곳을 가리키고 있으면 == 로 비교시 false가 나옵니다.)

 

 

[유제1-1]

Which will cause the longest execution of a sequential search looking for a value in an array of integers?

 

A. The value is the first one in the array
B. The value is in the middle of the array
C. The value is the last one in the array
D. The value isn't in the array

 

[유제1-2]

Which will cause the shortest execution of a sequential search looking for a value in an array of integers?

 

A. The value is the first one in the array
B. The value is in the middle of the array
C. The value is the last one in the array
D. The value isn't in the array

 

---

 

3.Binary Search

• Binary Search = 이진 탐색
• Binary Search는 미리 정렬되어있는 데이터(sorted data)를 대상으로 가운데 데이터부터 비교를 하여 나머지 절반은 버리면서 계속 가운데 부분을 비교해가는 알고리즘 입니다.
• Binary(이진) 라고 부르는 이유는, 한 번 비교를 할 때마다 Seach범위가 절반(1/2)으로 줄어들기 때문입니다.
• Sequential Search 보다 Binary Search가 훨씬 빠른 알고리즘입니다. 만약 70억명 인구 중에서 특정 정보를 찾으려고 할 때 Sequential Search는 평균 35억 번 비교해야 하고, Bineary Search는 최대 33번의 비교로 정보를 찾을 수 있습니다.
• Binary Search도 원하는 데이터를 찾게되면 그 데이터의 위치값(index)을 리턴하고, 찾지 못하면 -1을 리턴합니다.

 

 

[예제2-1]

아래의 int 데이터를 찾는 Binary Search 예제코드를 실행해 보세요.

public class BinSearchInt
{
    public static int binarySearch(int[] elements, int target)
    {
        int left = 0;
        int right = elements.length - 1;
        while (left <= right)
        {
            int middle = (left + right) / 2;
            if (target < elements[middle])
            {
                right = middle - 1;
            }
            else if (target > elements[middle])
            {
                left = middle + 1;
            }
            else
            {
                return middle;
            }
        }
        return -1;
    }
 
    public static void main(String[] args)
    {
        int[] arr1 = {-20, 3, 15, 81, 432};
 
        // test when the target is in the middle
        int index = binarySearch(arr1, 15);
        System.out.println(index);    // 2
 
        // test when the target is the first item in the array
        index = binarySearch(arr1, -20);
        System.out.println(index);    // 0
 
        // test when the target is in the array - last
        index = binarySearch(arr1, 432);
        System.out.println(index);    // 4
 
        // test when the target is not in the array
        index = binarySearch(arr1, 53);
        System.out.println(index);    // -1
    }
}

 

 

[예제2-2]

아래의 String 데이터를 찾는 Binary Search 예제코드를 실행해 보세요.

public class BinSearchStrings
{
    public static int binarySearch(String[] elements, String target)
    {
        int left = 0;
        int right = elements.length - 1;
        while (left <= right)
        {
            int middle = (left + right) / 2;
            if (target.compareTo(elements[middle]) < 0)
            {
                right = middle - 1;
            }
            else if (target.compareTo(elements[middle]) > 0)
            {
                left = middle + 1;
            }
            else
            {
                return middle;
            }
        }
        return -1;
    }
 
    public static void main(String[] args)
    {
        String[] arr1 = {"apple", "banana", "cherry", "kiwi", "melon"};
 
        // test when the target is in the middle
        int index = binarySearch(arr1, "cherry");
        System.out.println(index);    // 2
 
        // test when the target is the first item in the array
        index = binarySearch(arr1, "apple");
        System.out.println(index);    // 0
 
        // test when the target is in the array - last
        index = binarySearch(arr1, "melon");
        System.out.println(index);    // 4
 
        // test when the target is not in the array
        index = binarySearch(arr1, "pear");
        System.out.println(index);    // -1
    }
}
 

 

• Binary Search에서 문자열(String)을 비교할 때는 <, > 대신에 compareTo( ) 메소드를 사용해야 합니다.
• < , > 는 primitive types(int, double 등)에 사용하는 것입니다.

int compareTo(String other)  returns a negative value if the current string is less than the other string, 0 if they have the same characters in the same order, and a positive value if the current string is greater than the other string.

*compareTo( )에 대한 더 자세한 내용 링크 => https://wooduino.tistory.com/213

 

 

---

 

4.Runtimes

• 여러 알고리즘 중 어떤게 가장 효율적일지 판단하는 근거는 여러가지가 있을 수 있습니다.
• 그 근거로, 내가 가진 데이터의 상태(sorted, unsorted 등)가 있습니다.
• 그리고 다음 근거로, 알고리즘이 얼마나 빨리 실행되는지(runtimes)가 있습니다.
• Large data set에서 Binary Search는 Linear Search보다 더 빠르긴 하지만, Bineary Search는 반드시 정렬된 데이터(sorted data)이어야 합니다.
• 알고리즘에서 가장 최악의 경우(worst case behavior)는 실행시간이 가장 많이 걸리는 경우로서, 이는 내가 원하는 데이터가 없을 때 입니다.

 

아래 표는 데이터 개수가 N일 때, Linear Search와 Binary Search의 최악의 runtime을 나타냅니다.

N	Linear Search(비교 회수)	Binary Search(비교 회수)
2	2	2
4	4	3
8	8	4
16	16	5
100	100	7

 

 

• runtime은 수학적 방법으로 표현될 수 있습니다.
• 데이터 사이즈가 n일 때, Linear Search의 runtime은 n이고, Binary Search의 runtime은 log base of (n) 입니다.

 

 

 

(ex) Binary Search runtime of data N=130 => log base 2 of (130) => approximately 7 times

 

 

 

[유제2-1]

Which will cause the shortest execution of a binary search looking for a value in an array of integers?

 

A. The value is the first one in the array
B. The value is in the middle of the array
C. The value is the last one in the array
D. The value isn't in the array

 

 

[유제2-2]

Which of the following conditions must be true in order to search for a value using binary search?

 

I. The values in the array must be integers.
II. The values in the array must be in sorted order.
III. The array must not contain duplicate values.

 

A. I only
B. I and II
C. II only
D. II and III

 

[유제2-3]

How many times would the loop in the binary search run for an array int[] arr = {2, 10, 23, 31, 55, 86} with binarySearch(arr,55)?

 

A. 2
B. 1
C. 3

D. 4

 

 

[유제2-4]

If you had an ordered array of size 500, what is the maximum number of iterations required to find an element with binary search?

 

A. approximately 15 times
B. approximately 9 times
C. 500 times
D. 2 times

 

 

 

---

 

[유제 정답은 아래 "더보기" 클릭]

[유제1-1 정답]

D

(A sequential search loops through the elements of an array or list starting with the first and ending with the last and returns from the loop as soon as it finds the passed value. It has to check every value in the array when the value it is looking for is not in the array.)

 

[유제1-2 정답]

A

(This would only take one execution of the loop.)

 

[유제2-1 정답]

B

(If the value is in the middle of the array the binary search will return after one iteration of the loop.)

 

[유제2-2 정답]

C

 

[유제2-3 정답]

A

(It will first compare with the value at index 2 and then index 4 and then return 4.)

 

[유제2-4 정답]

B

(You can divide 500 in half, 9 times, or you can observe that 2^9 = 512 which is slightly bigger than 500.)

 

 

---