binary search

public class BinarySearch
{
public static void main(String[] args) {
int[] array = {0,1,2,3,6,7,8,9,10, 11, 12, 13, 14, 15, 16, 17, 18 , 19, 20, 21, 22, 23};


for (int i = 0; i < 23; i++) {
boolean result = BinarySearch.binarySearch(0, array.length-1, i, array);
if (result) System.out.println(i + " true");
else System.out.println(i + " false");
}
}

public static boolean binarySearch(int startIndex, int endIndex, int x,  int[] array) {

if (startIndex == -1 || endIndex == -1 || startIndex > endIndex) return false;

int centerIndex = (startIndex + endIndex) / 2;
if (array[centerIndex] == x) {
return true;
}
else if (array[centerIndex] > x) {
return binarySearch(startIndex, centerIndex-1, x, array);
}

else if (array[centerIndex] < x) {
return binarySearch(centerIndex+1, endIndex, x, array);
}

return false;
}
}


머리 속으로 그냥 바이너리 서치가 어떻게 되는지 아는 거랑 실제 코드 짜보는 거랑은
다소 차이가 있다.

직접 짜봐야 알게 되는 노하우도 있다.

예를 들면, 역시나, recursion을 쓸때에는

종료 조건을 잘 지정해줘야 하며, 특히나 배열과 index가지고 알고리즘 구할 때에는

여러 개의 인풋 케이스 생각해줘서 섬게하게 프로그래밍 하지 않으면, index 하나

잘못 놀린 게 잘못된 결과로 이어진다는 것을 생각해야 한다.

recursion은 좀 더 자연스럽게 쓸수 있도록 머리 회로를 구축해놔야 한다.