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

이진검색 - 루프사용(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 을 함으로써 배열의 크기와 상관없이 검색 할 수 있도록 설정