이진 탐색 (binarySearch) Java로 구현하기

이진탐색이란?

정렬된 배열에서 검색하고 싶은 키가 몇번째인지 확인 하는 탐색 알고리즘. ( 꼭 정렬이 되어 있어야 찾을 수 있다. )

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

-- 출처 https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

그럼 위 내용을 자바로 구현해보자

public class BinarySearch{

public static void main(String[] args) {

int[] arr = {1,3,5,9,10,15,20};

int idx = binarySearch(arr, 15); // 15가 어디 있는지 찾아보자

System.out.println("idx : " + idx);

}

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

int low = 0;

int high = arr.length;

while( low <= high ) {

int mid     = (low+high)/2;

int midVal = arr[mid];      // (low + high )/2 로 중간 값을 계속 구해간다.

if ( midVal < key ) {

low = mid+1;    // 중간 값이 찾으려는 값보다 작을 경우 low 인덱스를 중간인덱스 +1 로 변경

}else if ( midVal > key {

high = mid-1;  //  중간 값이 찾으려는 값보다 클 경우 high 인덱스를 중간 인덱스 -1로 변경

}else {

return mid;

}

  }

return -1;  // 없을 경우 -1 리턴

}

}

}

티스토리 에디터에서 직접 작성 했기 때문에 오타가 있을 수 있다.