이진탐색 binary search

Binary Search 이진탐색

// int 배열 

int list[] = {1,3,5,10,2,11, 13,14,15,18};

System.out.println();

// int 배열 정렬

Arrays.sort(list);

for(int a:list)

System.out.print(a+" ");

// 구현된 binary search

int findindex = binarySearch(list, 11);

System.out.println();

System.out.println("index"+findindex);

System.out.println("value"+list[findindex]);

// lo : low open , hi : high interval, arr 는 항상 오름차순 정렬되어 있다는 전제하에 수행

public static int binarySearch(int[] arr, int x){

int lo = -1; int hi = arr.length; int mid;

while(lo + 1 < hi){   // lo + 1 = hi 일때 종료됨 정의에 의해 항상 lo < hi 가 성립됨

mid = (lo + hi)/2;    // 중간값 index    

if (x==arr[mid]) return mid; // 찾았을경우 index 리턴

if (arr[mid] < x) 

   lo = mid;    // 중간값이 찾고자 하는 값보다 적을때 low 값을 mid 로 설정

else

hi = mid; // 중간값이 찾고자 하는 값보다 클때 high 값을 mid 로 설정

}

return -1; // 찾지 못하였을경우(없을경우) -1 리턴

}