알고리즘이 필요한 이유

정렬된 배열

정렬된 배열은 "전형적인" 배열과 거의 같다. 유일한 차이는 값을 추가 할 때마다 배열의 값을 정렬된 상태로 유지한다.

정렬된 배열은 값을 삽입하기 전에 먼저 검색을 수행해야한다. 그래야 데이터를 삽입해야 하는 위치를 정할 수 있다. 이게 전형적인 배열과 정렬된 배열의 성능 차이 중 하나이다.
정렬된 배열의 원소를 삽입 하는데는 최대 N + 2 시간 측정도를, 전형적인 배열이라면 최대 N + 1 시간 측정도를 가진다.
예로 오름차순으로 정렬된 배열에 가장 작은 값을 삽입한다고 생각해 보자.
0번 인덱스와 값을 비교하고 이 보다 삽입하는 값이 작기 때문에, 모든 인덱스를 오른쪽으로 한칸 씩 이동 시킨 후 인덱스 0에 값을 삽입한다. 따라서 최대 N + 2의 시간 측정도가 나오게 된다.

• 선형 검색
  정렬된 배열은 삽입에 전형적인 배열보다 덜 효육적이지만, 검색 연산에서는 매우 효율적이다.
  예로 위 그림에서 존재하지 않는 값인 23을 찾는다고 생각해보자.
  23은 17보다 크고 75보다 작으므로 검색 하는데 3단계가 필요하다.
  하지만 전형적인 배열은 모든 배열의 값을 선형 검색하므로 N만큼 걸리게 된다.
  하지만 두 배열의 모두 최대 시간 측정도는 선형 검색의 최대 시간인 N이다.

    static int sort(int[] arr, int number){
        for(int i = 0; i < arr.length; i++){
            if (arr[i] == number) return i; //값이 동일하면 그 해당 인덱스 반환       
            else if (arr[i] > number) break;//보다 크다면 종료.
        }
        return 0;
    }

하지만 정렬된 배열의 전형적인 배열보다 크게 두드런진 장정은 다른 검색 알고리즘을 사용 할 수 있다는 점이다. 이러한 알고리즘을 이진 검색이라 부르며, 이진 검색은 선형 검색보다 훨씬 빠르다.

• 이진 검색
  

임이의 값으로 이루어진 크기 9인 정렬된 배열에서 7을 찾는다고 해보자.
배열의 크기가 9이므로 9/2 = 4.5 -> 4인 것을 알 수 있다.
이 때 인덱스 4번의 값이 9라면, 0~3 인덱스 안에 찾는 값이 있다.
-> 4/2 = 2 -> 1, 인덱스 1의 값이 4라면 이제 인덱스 2, 3번에 7이 있다.
(4 + 1) / 2 = 2 -> 2번째 인덱스를 확인하고 해당 값이 아니라면 3번 째 인덱스를 확인한다.

• 코드 구현

    static int search(int[] arr, int number){
        int lb = 0;
        int ub = arr.length - 1;
        while (lb <= ub){
            int mp = (ub + lb) / 2;

        if (arr[mp] == number) return mp;
        else if (number < arr[mp]) ub = mp - 1;
        else lb = mp + 1;
    }
    return -1;
}

검색을 시작전에 배열 어디에든 있을 수 있으므로, 탐색 지점을 0과 최대 인덱스 번호로 초기화 시켜준다.
만약 중간 인덱스가 해당 값이라면 인덱스를 리턴한다.
해당 값이 아니고, 찾는 값보이 중간 값보다 작으면 그 앞부분에 해당하는 값을 찾을 수 있으므로 ub = mp - 1이다.
이와 반대로 찾는 값이 크다면 lb = mp + 1이다.
범위 원소가 0으로 좁혀진다면 찾는 값이 배열에 없다고 확실히 말 할 수 있다.
* **이진 검색과 선형 검색**
이진 작은 크기의 정렬된 배열이라면 선형 검색 알고리즘과 이진 검색 알고리즘의 큰 차이는 없다. 하지만 배열 더 커지게 차이가 점점 커지게 된다. 
크기가 100인 배열에서 각 검색에 필요한 최대 단계 수는 다음과 같다.
**선형 검색**: 100단계
**이진 검색**: 7단계
이진 검색은 검색 할 때마다 검색해야하는 셀의 절반을 제거 할 수 있다.
즉 이진 배열의 검색 단계가 한 단계 늘어나려면 크기가 두배 커져야한다.
하지만 선형 검색의 크기가 두배 늘어나면 단계도 두배 늘어난다.
![](https://velog.velcdn.com/images/chesthyen/post/148b3b8e-30a0-47fa-a928-b5bc784f9b0c/image.png)
>
정렬된 배열이 모든 상황에서 빠르건 아니다. 하지만 검색의 경우 훨씬 빠르다. 그렇기에 사용자의 애플리케이션에 어떤 구조가 더 좋은지 항상 분석하고 있어야 한다.