[검색] 선형탐색과 이진탐색

■ 선형검색 : 정렬되지 않은 데이터를 0부터 끝까지 확인할 때 유리

- 의사코드

for i from 0 to n-1
  if i'th element is the target value
     return true
  return false

- 자바코드

package linearSearch;

import java.util.Arrays;

public class LinearSearch1 {

	public static void main(String[] args) {
		int[] arr = new int[10];
		init(arr);
		System.out.println(Arrays.toString(arr));
		
		//linear search
		//전제 : 정렬되지 않은 데이터
		//찾으려는 수 : 5
		for (int i = 0; i < arr.length; i++) {
			if (arr[i]==5) {
				System.out.println("index : "+i);
				break;
			}
		}
	}
	
	public static void init(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int)(Math.random()*arr.length)+1;
			for (int j = 0; j < i; j++) {
				if (arr[i]==arr[j]) {
					i--;
					break;
				}
			}
		}
	}
}

>> 결과

[9, 3, 6, 8, 1, 5, 7, 4, 2, 10]
index : 5

 

■ 이진검색 : 정렬된 데이터들 안에서 특정 데이터를 찾을 때 유리

- 의사코드

*찾고자 하는 값이 50일 때,

if middle item is 50
	return true
else if 50 < middle item
	search left half
else if 50 > middle item 
	search right half

- 수학적 논리 : 중앙값을 지정한 후, left~right의 범위를 줄여가면서 logN의 속도로 탐색을 하는 방법

- 자바 코드

package BasicSearch;

public class _01_BinarySearch {

	public static void main(String[] args) {
		int[] arr = new int[] {1,2,3,4,5,6,7,8,9,10};
		int key = 3;
		
		int mid;
		int left = 0;
		int right = arr.length-1;
		while(left<=right) {
			mid = (left+right)/2;
			
			if(key==arr[mid]) {
				System.out.println("index : "+mid);
				break;
			}
			
			if(key < arr[mid]) {
				right = mid-1;
			}else if(key > arr[mid]) {
				left = mid+1;
			}
		}//end while
	}//end main

}

>> 결과

index : 2

 

 

※ 참조 : 자료구조에 대한 정리

https://why-dev.tistory.com/6?category=917883 

[컴퓨터 공학_복습] 알고리즘 정의, 검색과 정렬 알고리즘