'Algorithm&DataStructures/Searching'에 해당되는 글 2건

이진검색 - 루프사용(Binary Searching using loop)

- 가운데 요소들을 기준으로 양쪽으로 나누어 검색한다

- 찾는 요소와 가운데 요소의 크고 작음에 따라 방향이 결정된다

- 분할과 정복 기술 사용

- 빠르면 O(1) 최악이면 O(logn)의 성능을 갖는다

- 그러나 기존에 배열을 정렬 시킨 후 사용해야 한다

1. 구현

public class BinaryUsingLoop { public int binary(int arry[], int key){ int start = 0; int end = arry.length - 1; int mid; while(end >= start){ mid = (start + end)/2; if(arry[mid] == key){ return mid; } if(arry[mid] < key){ start = mid+1; }else{ end = mid-1; } } return -1; } public static void main(String[]args){ BinaryUsingLoop search = new BinaryUsingLoop(); int arry[] = {1,2,3,4,5,6,7,8,9}; System.out.println(search.binary(arry, 9)); } } <textarea> <br /></span></b></p>

- 중요한 점은 start와 end 부분을 설정 할때 +1, -1 을 함으로써 배열의 크기와 상관없이 검색 할 수 있도록 설정

단순 연속 검색 혹은 일직선 검색(Linear Searching, Sequential Searching)

- 배열안의 요소를 찾기위해 처음부터 하나씩 체크 한다

- 만약 요소가 없는 경우 최악의 성능을 제공한다. (배열을 처음부터 다 돌아야함)

1. 구현

public class LinearSearching { public int Linear(int a[], int key){ int size = a.length; for(int i = 0; i<size; i++){ if(a[i] == key){ return i; } } return -1; } public static void main(String[]args){ LinearSearching search = new LinearSearching(); int arry[] = {10,98,1,2}; System.out.println(search.Linear(arry, 2)); } }

- 실행 결과로 key에 해당하는 index 값을 반환한다

2. 결론

- 권장하지 않는다