#알고리즘_선형 탐색/이진 탐색 - Java

탐색 문제를 해결하는 방법 2가지 

• 선형 탐색(순차 검색) :  순서대로 하나씩 비교하면서 찾기
• 이진 탐색 : 반씩 범위를 줄여 나가면서 찾기

선형 탐색은 순서대로 하나씩 비교하면서 찾는 방법으로 시간 복잡도는 O(N)이다.

 

이진 탐색은 크기를 비교하며 반씩 줄여나가므로 배열이 정렬되어있다는 가정하에 진행한다. 따라서 배열이 정렬 되어있지 않다면 이진 탐색을 사용할 수 없다. 이진 탐색의 시간 복잡도는 O(log N)이다.

 

이진 탐색의 장점은 선형 탐색보다 탐색 속도가 빠르지만, 정렬되어 있어야 한다는 단점이 있다.

 

이진 탐색의 메카니즘

정렬된 배열의 중간에 임의의 값을 찾고자하는 값과 비교하여

1) 만약 중간의 값이 더 작다면 중간의 값을 제외한 배열의 우측 데이터들을 대상으로 탐색을 진행한다.

2) 만약 중간의 값이 더 크다면 중간의 값을 제외한 배열의 좌측 데이터들을 대상으로 탐색을 진행한다.

3) 1,2) 를 반복하며 만약 중간의 값과 찾고자 하는 값이 동일하다면 알고리즘을 중단한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

import java.util.Arrays;   public class search {     public static void main(String[] args) {         int arr[] = { 12,4,7,2,9,15,29,41};         System.out.println(linear_search(arr, 2));                  Arrays.sort(arr);         System.out.println(binary_search(arr, 2));     }          public static int linear_search(int arr[], int val) {                  for(int i=0; i<arr.length; i++) {             if(arr[i] == val) {                 return i;             }         }         return -1;     }          public static int binary_search(int arr[], int val) {           int begin = 0;         int end = arr.length-1;         int middle;                  while(begin<=end) {             middle = (begin+end)/2;             if(val == arr[middle])                 return middle;             else if(val > arr[middle]) {                 begin = middle + 1;             }else {                 end = middle-1;             }         }         return -1;     } }   Colored by Color Scripter

cs