상세 컨텐츠

본문 제목

[TDD] 이진 검색

IT/프로그래밍

by James Lee. 2015. 12. 6. 19:50

본문

TDD를 사용한 이진 검색


요구사항.

1~10000까지의 정수를 입력받고 이진 검색을 통하여 걸린 횟수를 출력


ex) 1~100을 찾을때

47 입력시 검색 비교값인 7을 반환

63 입력시 검색 비교값인 6을 반환


독립된 기능 정의 (설계)

  1. 저장소의 생성과 초기화 (배열의 크기를 정수값으로 입력하면 그 만큼의 배열이 생성됨, 배열은 순차적으로 1~ 배열의 크기 만큼 채워져 있음)
  2. 검색 (검색 대상 값과, 배열을 입력하면 이진 탐색 후 걸린 횟수를 반환, 값이 없을시 0을 반환)
  3. 결과 (결과 값을 받아서 검색 성공여부를 판단)

첫번째 TDD Cycle

저장소의 생성과 초기화

실패하는 테스트 코드 작성


1~10의 값이 저장되어 있는 testAry배열과 1~10의 값이 채워진 10개의 크기의 배열을 생성하는 용도의 bs.initArray(10); 비교

public void initArrayTest() {
  int[] testAry = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  assertArrayEquals(testAry, bs.initArray(10));
 }


프로덕션 코드 초기 모습

 public int[] initArray(int arySize) {
  return null;
 }


처리를 아무것도 해주지 않은 initArray는 null을 반환한다.

이는 테스트 코드의 testAry배열과 같지 않으므로 테스트 통과는 실패한다.


테스트 코드 통과시키기

가장 간단하게 테스트를 통과시켜 본다.

테스트 코드에 있는 testAry배열을 그대로 가져온다.

 public int[] initArray(int arySize) {
  int[] testAry = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  return testAry;
 }

테스트 코드는 통과한다.

리팩토링

배열의 이름을 수정한다.

값을 저장하는 배열을 반환하는 것이므로 testAry보다는 storeAry가 더 적당하다.

 public int[] initArray(int arySize) {
  int[] storeAry = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  return storeAry;
 }

리팩토링

반복문을 이용하여 배열의 값을 간단하게 초기화한다.

public int[] initArray(int arySize) {
  int[] storeAry = new int[10];
  for (int i = 0; i < 10; i++) {
   storeAry[i] = i + 1;
  }
  return storeAry;
 }


리팩토링

for문에 있는 최대 반복횟수인 10은 배열의 길이의 값과 같다.

 public int[] initArray(int arySize) {
  int[] storeAry = new int[10];
  for (int i = 0; i < storeAry.length; i++) {
   storeAry[i] = i + 1;
  }
  return storeAry;
 }


리팩토링

배열을 생성할때 배열의 크기 10은 매개변수로 들어오는 arySize의 값과 같다.

 public int[] initArray(int arySize) {
  int[] storeAry = new int[arySize];
  for (int i = 0; i < storeAry.length; i++) {
   storeAry[i] = i + 1;
  }
  return storeAry;
 }

리팩토링

리팩토링 할 것이 없다.


코드 커밋하기


다른 값 테스트해보기

initArray의 값이 다른 값을 가진 배열에도 동작하는지 알아보기 위해 코드를 추가했다.

코드는 잘 동작한다.

배열을 생성하고 초기화시키는 메소드는 일반화되었다고 판단한다.

 public void initArrayTest() {
  int[] testAry = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  assertArrayEquals(testAry, bs.initArray(10));
  int[] testAry2 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
    16, 17, 18, 19, 20 };
  assertArrayEquals(testAry2, bs.initArray(20));
 }


두번째 TDD Cycle

이진 탐색 및 걸린 횟수 반환, 검색 실패시 0 반환

실패하는 테스트 코드 작성

1~100까지의 수 중 47을 이진탐색하면 6번만에 검사한다.

  public void binarySearchTest() {
  assertEquals(7, bs.binarySearch(47,bs.initArray(100)));
 }

프로덕션 코드 초기 모습

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  return searchCount;
 }

프로덕션 코드는 0을 반환하기 때문에 테스트 코드는 실패한다.

테스트 코드 통과시키기

프로덕션 코드를 아래와 같이 수정한다.

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  searchCount=6;
  return searchCount;
 }

테스트 통과


리팩토링

코드를 다음과 같이 바꿀 수 있다. (계속 중복에 가깝게 바꾼다).

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  searchCount++;
  searchCount++;
  searchCount++;
  searchCount++;
  searchCount++;
  searchCount++;
  return searchCount;
 }

리팩토링

47이 탐색되는 과정을 조건문으로 포함한다.

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  if (47 < 50) {
   searchCount++;
  }
  if (47 > 25) {
   searchCount++;
  }
  if (47 > 37) {
   searchCount++;
  }
  if (47 > 43) {
   searchCount++;
  }
  if (47 > 46) {
   searchCount++;
  }
  if (47 == 47) {
   searchCount++;
  }
  return searchCount;
 }


리팩토링

47은 비교대상인 searchValue와 의미가 같기 때문에 파라미터로 들어온 searchValue로 수정한다.

  public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  if (searchValue < 50) {
   searchCount++;
  }
  if (searchValue > 25) {
   searchCount++;
  }
  if (searchValue > 37) {
   searchCount++;
  }
  if (searchValue > 43) {
   searchCount++;
  }
  if (searchValue > 46) {
   searchCount++;
  }
  if (searchValue == 47) {
   searchCount++;
  }
  return searchCount;
 }


리팩토링

검색된 값은 과 비교되는 값을 compareValue로 정의한다.

그리고 이 compareValue에 50을 기준으로 이전의 값의 절반인 숫자가 더해지거나 빼지는 것을 볼 수 있다.

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue;
  compareValue = 50;
  if (searchValue < compareValue) {
   searchCount++;
  }
  compareValue = 25; // -25
  if (searchValue > compareValue) {
   searchCount++;
  }
  compareValue = 37; // + 12
  if (searchValue > compareValue) {
   searchCount++;
  }
  compareValue = 43; // + 6
  if (searchValue > compareValue) {
   searchCount++;
  }
  compareValue = 46; // + 3
  if (searchValue > compareValue) {
   searchCount++;
  }
  compareValue = 47; // + 1
  if (searchValue == compareValue) {
   searchCount++;
  }
  return searchCount;
 }


리팩토링

비교대상인 compareValue에 50을 기준으로 절반씩 줄어든 값 tmp를 (이름은 일단 임시로 tmp로 지정했다.) 더하거나 빼준다.

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue;
  int tmp = 50;
  compareValue = 50;
  if (searchValue < compareValue) {
   searchCount++;
  }
  tmp /= 2;
  compareValue -= tmp; // -25
  if (searchValue > compareValue) {
   searchCount++;
  }
  tmp /= 2;
  compareValue += tmp; // + 12
  if (searchValue > compareValue) {
   searchCount++;
  }
  tmp /= 2;
  compareValue += tmp; // + 6
  if (searchValue > compareValue) {
   searchCount++;
  }
  tmp /= 2;
  compareValue += tmp; // + 3
  if (searchValue > compareValue) {
   searchCount++;
  }
  tmp /= 2;
  compareValue += tmp; // + 1
  if (searchValue < compareValue) {
   searchCount++;
  }
  tmp /= 2;
  if (searchValue == compareValue) {
   searchCount++;
  }
  return searchCount;
 }

리팩토링

규칙성을 보여주기 위하여 아래의 형태로 정의했다

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = 100;
  int tmp = 50;

  compareValue -= tmp;
  tmp /= 2;
  if (searchValue < compareValue) {
   searchCount++;
  }
  compareValue -= tmp; // -25
  
  tmp /= 2;
  if (searchValue > compareValue) {
   searchCount++;
  }
  compareValue += tmp; // + 12
  
  tmp /= 2;
  if (searchValue > compareValue) {
   searchCount++;
  }
  compareValue += tmp; // + 6
  
  tmp /= 2;
  if (searchValue > compareValue) {
   searchCount++;
  }
  compareValue += tmp; // + 3
  
  tmp /= 2;
  if (searchValue > compareValue) {
   searchCount++;
  }
  compareValue += tmp; // + 1
  
  if (searchValue == searchValue) {
   searchCount++;
  }
  return searchCount;
 }

리팩토링

어떤 경우에는 더하고

어떤 경우에는 빼는가?

이전의 검색값이 기준보다 작으면 빼고

이전의 검색값이 기준보다 크면 더한다

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = 100;
  int tmp = 50;
  compareValue -= tmp;
  tmp /= 2;
  if (searchValue < compareValue) {
   searchCount++;
   compareValue -= tmp;
  } else {
   compareValue += tmp;
  }
  tmp /= 2;
  if (searchValue > compareValue) {
   searchCount++;
   compareValue += tmp;
  } else {
   compareValue -= tmp;
  }
  tmp /= 2;
  if (searchValue > compareValue) {
   searchCount++;
   compareValue += tmp;
  } else {
   compareValue -= tmp;
  }
  tmp /= 2;
  if (searchValue > compareValue) {
   searchCount++;
   compareValue += tmp;
  } else {
   compareValue -= tmp;
  }
  tmp /= 2;
  if (searchValue < compareValue) {
   searchCount++;
  }
  if (searchValue == searchValue) {
   searchCount++;
  }
  return searchCount;
 }

리팩토링

searchValue가 compareValue보다 큰 경우의 코드 내용이 모두 동일했기에

반복문으로 중복을 제거하였다.

  public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = 100;
  int tmp = 50;
  compareValue -= tmp;
  tmp /= 2;
  if (searchValue < compareValue) {
   searchCount++;
   compareValue -= tmp;
  } else {
   compareValue += tmp;
  }
  for (int i = 0; i < 4; i++) {
   tmp /= 2;
   if (searchValue > compareValue) {
    searchCount++;
    compareValue += tmp;
   } else {
    compareValue -= tmp;
   }
  }
  if (searchValue == searchValue) {
   searchCount++;
  }
  return searchCount;
 }


리팩토링

아래의 for반복문에서는 searchValue가 compareValue보다 큰 경우의 소스만 줄인 것이다.

따라서 for 내부의 searchCount는 무조건 실행된다.

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = 100;
  int tmp = 50;
  
  compareValue -= tmp;
  tmp /= 2;
  
  if (searchValue < compareValue) {
   searchCount++;
   compareValue -= tmp;
  } else {
   compareValue += tmp;
  }
  for (int i = 0; i < 4; i++) {
   tmp /= 2;
   if (searchValue > compareValue) {  //항상 searchValue가 compareValue보다 크다
    searchCount++;// 무조건 실행된다.
    compareValue += tmp;
   } else {
    compareValue -= tmp;
   }
  }
  if (searchValue == searchValue) {
   searchCount++;
  }
  return searchCount;
 }


따라서 for 내부의 searchCount는 조건문 밖으로 내보낸다.

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = 100;
  int tmp = 50;
  compareValue -= tmp;
  tmp /= 2;
  if (searchValue < compareValue) {
   searchCount++;
   compareValue -= tmp;
  } else {
   compareValue += tmp;
  }
  for (int i = 0; i < 4; i++) {
   tmp /= 2;
   if (searchValue > compareValue) {
    compareValue += tmp;
   } else {
    compareValue -= tmp;
   }
   searchCount++; //조건문 밖으로 내보냄
  }
  if (searchValue == searchValue) {
   searchCount++;
  }
  return searchCount;
 }


마찬가지로 100에서 47을 탐색하는 경우 첫 조건문  if(searchValue < compareValue)는 참이고, searchCount는 무조건 실행되게 된다.

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = 100;
  int tmp = 50;
  compareValue -= tmp;
  tmp /= 2;
  if (searchValue < compareValue) { //searchValue는 compareValue보다 작음
   searchCount++; //무조건 실행됨
   compareValue -= tmp;
  } else {
   compareValue += tmp;
  }
  for (int i = 0; i < 4; i++) {
   tmp /= 2;
   if (searchValue > compareValue) {
    compareValue += tmp;
   } else {
    compareValue -= tmp;
   }
   searchCount++;
  }
  if (searchValue == searchValue) {
   searchCount++;
  }
  return searchCount;
 }

따라서 이곳의 if문에서도 searchCount를 밖으로 빼준다.

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = 100;
  int tmp = 50;
  compareValue -= tmp;
  tmp /= 2;
  if (searchValue < compareValue) {
   compareValue -= tmp;
  } else {
   compareValue += tmp;
  }
  searchCount++;
  for (int i = 0; i < 4; i++) {
   tmp /= 2;
   if (searchValue > compareValue) {
    compareValue += tmp;
   } else {
    compareValue -= tmp;
   }
   searchCount++;
  }
  if (searchValue == searchValue) {
   searchCount++;
  }
  return searchCount;
 }


리팩토링

윗쪽의 if문의 조건을 반대로 바꿔서

  if (searchValue < compareValue) {
   compareValue -= tmp;
  } else {
   compareValue += tmp;
  }

아래와 같이 수정한다.

   if (searchValue > compareValue) {
    compareValue += tmp;
   } else {
    compareValue -= tmp;
   }


이제 if문의 내용이 완전히 중복된다.

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = 100;
  int tmp = 50;
  compareValue -= tmp;
  tmp /= 2;
  if (searchValue > compareValue) { //if문의 내용이 동일하다
   compareValue += tmp;
  } else {
   compareValue -= tmp;
  }
  searchCount++;
  for (int i = 0; i < 4; i++) {
   tmp /= 2;
   if (searchValue > compareValue) { //if문의 내용이 동일하다
    compareValue += tmp;
   } else {
    compareValue -= tmp;
   }
   searchCount++;
  }
  if (searchValue == searchValue) {
   searchCount++;
  }
  return searchCount;
 }

리팩토링

중복되는 if문을 반복문 내부로 옮겨서 합친다

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = 100;
  int tmp = 50;
  compareValue -= tmp;
  for (int i = 0; i < 5; i++) {
   tmp /= 2;
   if (searchValue > compareValue) {
    compareValue += tmp;
   } else {
    compareValue -= tmp;
   }
   searchCount++;
  }
  if (searchValue == compareValue) {
   searchCount++;
  }
  return searchCount;
 }


리팩토링

초기 compareValue에 들어가는 100은 배열의 크기, compareValue에 들어가는 50은 compareValue의 절반의 값이므로 아래와 같이 수정한다.

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = initArray.length;
  int tmp = compareValue / 2;
  compareValue -= tmp;
  for (int i = 0; i < 5; i++) {
   tmp /= 2;
   if (searchValue > compareValue) {
    compareValue += tmp;
   } else {
    compareValue -= tmp;
   }
   searchCount++;
  }
  if (searchValue == compareValue) {
   searchCount++;
  }
  return searchCount;
 }


리팩토링

아래의 조건문을 for문 내부로 이동시켰다.

if (searchValue == compareValue) {

    searchCount++;
}
 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = initArray.length;
  int tmp = compareValue / 2;
  compareValue -= tmp;
  for (int i = 0; i < 6; i++) {
   tmp /= 2;
   searchCount++;
   if (searchValue == compareValue) {
    break;
   } else if (searchValue > compareValue) {
    compareValue += tmp;
   } else {
    compareValue -= tmp;
   }
  }
  return searchCount;
 }


리팩토링

아래의 조건문을 for문 내부로 이동시켰다.

if (searchValue == compareValue) {

    searchCount++;
}
 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = initArray.length;
  int tmp = compareValue / 2;
  compareValue -= tmp;
  for (int i = 0; i < 6; i++) {
   tmp /= 2;
   searchCount++;
   if (searchValue == compareValue) {
    break;
   } else if (searchValue > compareValue) {
    compareValue += tmp;
   } else {
    compareValue -= tmp;
   }
  }
  return searchCount;
 }


리팩토링

초기값이 campareValue는 50, tmp는 25로 시작하므로 아래와 같이 수정할 수 있다.
 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = initArray.length / 2; 
  int tmp = compareValue / 2; 
  while (true) {
   searchCount++;
   if (searchValue == compareValue) {
    break;
   } else if (searchValue > compareValue) {
    compareValue += tmp;
   } else {
    compareValue -= tmp;
   }
   tmp /= 2;
  }
  return searchCount;
 }


리팩토링

tmp변수의 변수명이 모호하므로 compareValue를 조정한다는 의미인 adjustCompareValue로 수정한다.
 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = initArray.length / 2; 
  int adjustCompareValue = compareValue / 2; 
  // 시작할때 campareValue는 50, tmp는 25로 시작
  while (true) {
   searchCount++;
   if (searchValue == compareValue) {
    break;
   } else if (searchValue > compareValue) {
    compareValue += adjustCompareValue;
   } else {
    compareValue -= adjustCompareValue;
   }
   adjustCompareValue /= 2;
  }
  return searchCount;
 }

더이상 리팩토링 할 부분이 없다고 판단하여 작성한 코드를 커밋한다.

코드 커밋하기


솔루션 일반화 테스트

작성한 코드가 다른 값들에도 적용되는지 여러 경우를 넣어서 테스트해본다.

assertEquals(0, bs.binarySearch(101,bs.initArray(100))); 에서 실패하는것을 확인할 수 있다.

이유는 searchValue로 들어온 101이 배열 내부에 없기 때문에 while문이 무한반복되기 때문이다.

 public void binarySearchTest() {
  assertEquals(6, bs.binarySearch(47,bs.initArray(100)));
  assertEquals(1, bs.binarySearch(50,bs.initArray(100)));
  assertEquals(2, bs.binarySearch(25,bs.initArray(100)));
  assertEquals(3, bs.binarySearch(63,bs.initArray(100)));
  assertEquals(0, bs.binarySearch(101,bs.initArray(100))); //실패
 }


통과하는 테스트 코드 작성

searchValue의 값으로 101이 들어왔을때 0을 반환하도록 작성한다. 테스트는 통과한다.

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = initArray.length / 2;
  int adjustCompareValue = compareValue / 2;
  if (searchValue == 101) {
   searchCount = 0;
  } else {
   // 시작할때 campareValue는 50, tmp는 25로 시작
   while (true) {
    searchCount++;
    if (searchValue == compareValue) {
     break;
    } else if (searchValue > compareValue) {
     compareValue += adjustCompareValue;
    } else {
     compareValue -= adjustCompareValue;
    }
    adjustCompareValue /= 2;
   }
  }
  return searchCount;
 }


리팩토링

현재로써는 리팩토링 할 부분이 없다.


코드 커밋하기


실패하는 테스트 코드 작성

이번에는 searchValue에 -5를 넣었다. 역시 배열에 없는 값이므로 while문이 무한반복되게 되어 테스트코드는 실패한다.

 public void binarySearchTest() {
  assertEquals(6, bs.binarySearch(47,bs.initArray(100)));
  assertEquals(1, bs.binarySearch(50,bs.initArray(100)));
  assertEquals(2, bs.binarySearch(25,bs.initArray(100)));
  assertEquals(3, bs.binarySearch(63,bs.initArray(100)));
  assertEquals(0, bs.binarySearch(101,bs.initArray(100))); //실패
  assertEquals(0, bs.binarySearch(-5,bs.initArray(100))); //실패
 }


테스트 코드 통과시키기

탐색값으로 -5가 들어오면 0을 반환하도록 작성. 테스트 코드는 통과한다.

 public int binarySearch(int searchValue, int[] initArray) {
  int searchCount = 0;
  int compareValue = initArray.length / 2;
  int adjustCompareValue = compareValue / 2;
  if (searchValue == 101) {
   searchCount = 0;
  } else if (searchValue == -5) {
   searchCount = 0;
  } else {
   // 시작할때 campareValue는 50, tmp는 25로 시작
   while (true) {
    searchCount++;
    if (searchValue == compareValue) {
     break;
    } else if (searchValue > compareValue) {
     compareValue += adjustCompareValue;
    } else {
     compareValue -= adjustCompareValue;
    }
    adjustCompareValue /= 2;
   }
  }
  return searchCount;
 }

TDD를 사용한 이진 검색 2

요구사항 재정의

이사님께서 요구사항을 재정의 하셨다.

그리고 요구사항 분석에 대한 설명을 해주셨다.

 테스트 주도 개발 > 요구사항분석.png" class="confluence-embedded-image" style="cursor: move; max-width: 100%;" src="http://wiki.wiselog.com/download/attachments/18226110/%EC%9A%94%EA%B5%AC%EC%82%AC%ED%95%AD%EB%B6%84%EC%84%9D.png?version=1&modificationDate=1423618825000&api=v2" data-mce-src="http://wiki.wiselog.com/download/attachments/18226110/%EC%9A%94%EA%B5%AC%EC%82%AC%ED%95%AD%EB%B6%84%EC%84%9D.png?version=1&modificationDate=1423618825000&api=v2" data-location="[개발본부] Study > 테스트 주도 개발 > 요구사항분석.png" data-linked-resource-container-id="18226110" data-base-url="http://wiki.wiselog.com" data-linked-resource-default-alias="요구사항분석.png" data-linked-resource-type="attachment" data-linked-resource-id="18320682" data-image-src="/download/attachments/18226110/%EC%9A%94%EA%B5%AC%EC%82%AC%ED%95%AD%EB%B6%84%EC%84%9D.png?version=1&modificationDate=1423618825000&api=v2">


느낀점

  1. 지금껏 하나의 실패 케이스를 완벽하게 완성한 뒤, 다른 경우의 수를 넣었었는데, 이 방법보다는 두세개의 실패 케이스(경계를 가진 것.. ex) -1, 0, 1)를 작성하고  공통된 부분을 추출하는 것이 솔루션 일반화에 더 도움이 된다는 것을 느꼈다. (윗부분의 이진검색에서 값 검색 실패시 무한반복문이 실행될때, 값을 수정하기 애매했다.)
  2. 요구사항 분석을 명확히 하는 것이 중요하다. 왜냐하면 이것을 명확히 해야, 나중에 요구사항과 다른 부분을 수정하기 위해 작성한 코드를 뒤엎는 일을 방지할 수 있기 때문이다.


다시 요구사항을 정리해보자.

요구사항 정리

  1. 검색할 자료구조는 배열이다.
  2. 배열에는 임의의 정수가 들어간다.
  3. 배열은 오름차순으로 정렬되어있다.
  4. 배열의 크기는 사용자가 입력하는 만큼 생성된다.
  5. 검색의 결과는 true와 false로 나타낸다.

프로그램 설계

  1. 배열 가져오기 (input : 배열의 크기, output : 생성된 배열)
    1. 사용자가 입력한 크기만큼 자동으로 생성
    2. 임의의 정수로 초기화
    3. 오름차순으로 정렬하여 반환한다.
  2. 값 탐색 (input : 검색할 값, output : 검색 결과)
    1. 검색할 값을 입력
    2. 배열을 가져옴
    3. 이진탐색의 알고리즘에 따라 값 탐색
    4. 값이 있으면 true, 값이 없으면 false를 반환



첫번째 TDD Cycle

실패하는 테스트 코드 작성

프로덕션 코드의 초기 형태를 작성한다.

이진 탐색의 결과를 반환하는 getResult 메소드이다.

  public boolean getResult(int searchValue)
 {
  return false;
 }


테스트 코드를 작성한다.

프로덕션 코드는 아무런 처리도 하지 않고 false를 기본으로 반환하기 때문에 테스트 코드는 실패한다

 public void binarySearchTest() {
  assertEquals(true, bs.getResult(47));
 }


테스트 코드 통과시키기

검색 대상으로 들어온 값이 47이면 true를 반환하여 테스트 코드를 통과하도록 하였다.

  public boolean getResult(int searchValue) {
  if (searchValue == 47) {
   return true;
  }
  return false;
 }


리팩토링

여기서 return true와 false는 반환하는 결과값이기 때문에 result라는 변수명의 값으로 정의했다.

  public boolean getResult(int searchValue) {
  boolean result = false;
  if (searchValue == 47) {
   result = true;
  }
  return result;
 }


코드 커밋


두번째 TDD Cycle

실패하는 테스트 코드 만들기

테이블의 두번째 행인 1을 넣었을때 false가 나오는 값을 검사하는 테스트 코드를 만든다

  public void binarySearchTest() {
  assertEquals(true, bs.getResult(47));
  assertEquals(false, bs.getResult(1));
 }

테스트 코드를 무조건 실패하도록 만들기 위하여 1이 들어오면 반환값이 true가 나오도록 설정한다.

 public boolean getResult(int searchValue) {
  boolean result = false;
  if (searchValue == 47) {
   result = true;
  }
  if (searchValue == 1) {
   result = true;
  }
  return result;
 }


테스트 코드 통과시키기

1이 들어왔을때에 false가 반환되도록 한다.

 

리팩토링

배열을 가져오는 기능을 추가한다. (이 기능은 이 문제에서는 자세히 다루지 않기로 한다. )

 public int[] getArray() {
  int[] array = { 0 };
  return array;
 }

 public boolean getResult(int searchValue) {
  boolean result = false;
  int[] ary = getArray();
  if (searchValue == 47) {
   result = true;
  }
  if (searchValue == 1) {
   result = false;
  }
  return result;
 }


코드 커밋하기

실패하는 테스트 케이스 만들기

배열에서 0을 탐색했을시에 true를 반환하는 테스트 코드를 작성.

  public void binarySearchTest() {
  assertEquals(true, bs.getResult(47));
  assertEquals(false, bs.getResult(1));
  assertEquals(true, bs.getResult(0));
 }


테스트코드를 실패시키기 위하여 0이 들어오면 false를 반환하도록 한다.

 public boolean getResult(int searchValue) {
  boolean result = false;
  int[] ary = getArray();
  if (searchValue == 47) {
   result = true;
  }
  if (searchValue == 1) {
   result = false;
  }
  if (searchValue == 0) {
   result = false;
  }
  return result;
 }

테스트 코드 통과시키기

테스트 코드를 통과시키기 위하여 프로덕션 코드를 수정한다

 public boolean getResult(int searchValue) {
  boolean result = false;
  int[] ary = getArray();
  if (searchValue == 47) {
   result = true;
  }
  if (searchValue == 1) {
   result = false;
  }
  if (searchValue == 0) {
   result = true;
  }
  return result;
 }


리팩토링

중복이 보이지만 요구사항 테이블에 있는 케이스들을 작성할때까지는 리팩토링을 잠시 보류한다.

코드 커밋


실패하는 테스트 케이스 만들기

배열에서 -1을 탐색했을시에 false를 반환하는 테스트 코드를 작성.

  public void binarySearchTest() {
  assertEquals(true, bs.getResult(47));
  assertEquals(false, bs.getResult(1));
  assertEquals(true, bs.getResult(0));
  assertEquals(false, bs.getResult(-1));
 }


테스트코드를 실패시키기 위하여 -1이 들어오면 true를 반환하도록 한다.

 public boolean getResult(int searchValue) {
  boolean result = false;
  int[] ary = getArray();
  if (searchValue == 47) {
   result = true;
  }
  if (searchValue == 1) {
   result = false;
  }
  if (searchValue == 0) {
   result = false;
  }
  if (searchValue == -1) {
   result = true;
  }
  return result;
 }

테스트 코드 통과시키기

테스트 코드를 통과시키기 위하여 프로덕션 코드를 수정한다

 public boolean getResult(int searchValue) {
  boolean result = false;
  int[] ary = getArray();
  
  if (searchValue == 47) {
   result = true;
  }
  if (searchValue == 1) {
   result = false;
  }
  if (searchValue == 0) {
   result = false;
  }
  if (searchValue == -1) {
   result = false;
  }
  return result;
 }

테스트 코드가 통과한다.

리팩토링

이제 요구사항 테이블에 나열된 배열 1개일때의 경우가 모두 나왔으므로 리팩토링을 시작한다.

요구사항에 보다 적합하게 만들기 위하여 getArray 메소드를 없애고 그때그때 비교할 수 있도록 배열의 초기화 구간을 구분하였다

  public boolean getResult(int searchValue) {
  boolean result = false;
  int[] ary;
  // 배열이 초기화되지 않았을 때
  ary = new int[0];
  if (searchValue == 47) {
   result = true;
  }
  // 1개의 배열, 0이 들어있을 때
  ary = new int[1];
  ary[0] = 0;
  if (searchValue == 1) {
    result = false;
   }
  }
  if (searchValue == 0) {
    result = true;
  }
  if (searchValue == -1) {
    result = false;
  }
  return result;
 }

리팩토링

모든 탐색 값들은 배열의 각 요소와 비교를 거치고 result에 값을 넣기 때문에 if문으로 배열의 요소와 값을 비교해준다.

  public boolean getResult(int searchValue) {
  boolean result = false;
  int[] ary;
  // 배열이 초기화되지 않았을 때
  ary = new int[0];
  if (searchValue == 47) {
   result = true;
  }
  // 1개의 배열, 0이 들어있을 때
  ary = new int[1];
  ary[0] = 0;
  if (searchValue == 1) {
   if (searchValue == ary[0]) {
    result = false;
   }
  }
  if (searchValue == 0) {
   if (searchValue == ary[0])
    result = true;
  }
  if (searchValue == -1) {
   if (searchValue == ary[0])
    result = false;
  }
  return result;
 }


리팩토링

코드를 분석해 보면 다음과 같은 공통점을 찾을 수 있다.

  public boolean getResult(int searchValue) {
  boolean result = false;
  int[] ary;
  // 배열이 초기화되지 않았을 때
  ary = new int[0];
  if (searchValue == 47) {
   result = true;
  }
  // 1개의 배열, 0이 들어있을 때
  ary = new int[1];
  ary[0] = 0;
  
  if (searchValue == 1) { // 배열의 요소(0)와 일치하지 않을 때
   if (searchValue == ary[0]) {
    result = false;
   }
  }
  if (searchValue == 0) { //배열의 요소(0)와 일치할 때
   if (searchValue == ary[0])
    result = true;
  }
  if (searchValue == -1) { //배열의 요소(0)와 일치하지 않을 때
   if (searchValue == ary[0])
    result = false;
  }
  return result;
 }

리팩토링

배열을 테스트 코드 쪽으로 옮겨서 각 배열마다 검사를 다르게 할 수 있도록 하였다.

테스트 코드

  public void binarySearchTest() {
  int[] ary = new int[0];
  // 배열 초기화 안됬을때
  assertEquals(true, bs.getResult(47, ary));
  ary = new int[1];
  ary[0] = 0;
  // 1개짜리 배열에 0만 들어가 있을때
  assertEquals(false, bs.getResult(1, ary));
  assertEquals(true, bs.getResult(0, ary));
  assertEquals(false, bs.getResult(-1, ary));
 }


프로덕션 코드

  public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  if (ary.length == 1) {
   // 1개의 배열, 0이 들어있을 때
   if (searchValue == 0) { // 배열의 요소(0)와 일치할 때
    if (searchValue == ary[0])
     result = true;
   }
   if (searchValue == 1) { // 배열의 요소(0)와 일치하지 않을 때
    if (searchValue == ary[0]) {
     result = false;
    }
   }
   if (searchValue == -1) { // 배열의 요소(0)와 일치하지 않을 때
    if (searchValue == ary[0])
     result = false;
   }
  } else {
   // 배열이 초기화되지 않았을 때
   if (searchValue == 47) {
    result = true;
   }
  }
  return result;
 }

리팩토링

배열의 요소와 일치하지 않을때의 코드의 중복을 제거하였다.

  public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  if (ary.length == 1) {
   if (searchValue == 0) { // 배열의 요소(0)와 일치할 때
    if (searchValue == ary[0])
     result = true;
   }
   if (searchValue != ary[0]) { // 배열의 요소(0)와 일치하지 않을 때
    result = false;
   }
  } else {
   if (searchValue == 47) {
    result = true;
   }
  }
  return result;
 }

리팩토링

   if (searchValue == 0) { // 배열의 요소(0)와 일치할 때
    if (searchValue == ary[0])
     result = true;
   }

이 부분에서 비교하는 0 부분은 ary[0]이므로 의미가 없어진 바깥쪽 if문을 제거한다.

  public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  if (ary.length == 1) {
   if (searchValue == ary[0])
    result = true;
   if (searchValue != ary[0]) { // 배열의 요소(0)와 일치하지 않을 때
    result = false;
   }
  } else {
   if (searchValue == 47) {
    result = true;
   }
  }
  return result;
 }

리팩토링

 두개의 if문을 하나의 if-else구문으로 합칠 수 있다.

  public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  if (ary.length == 1) {
   if (searchValue == ary[0])
    result = true;
   else {
    result = false;
   }
  } else {
   if (searchValue == 47) {
    result = true;
   }
  }
  return result;
 }

코드 커밋하기


세번째 TDD Cycle

실패하는 테스트 코드 작성

두개의 배열을 만들고 0,4의 값을 넣어서 테스트해본다.
요구사항 테이블에 있는 값들을 테스트한다. 

  public void binarySearchTest() {
  int[] ary = new int[0];
  // 배열 초기화 안됬을때
  assertEquals(true, bs.getResult(47, ary));
  ary = new int[1];
  ary[0] = 0;
  // 1개짜리 배열에 0만 들어가 있을때
  assertEquals(false, bs.getResult(1, ary));
  assertEquals(true, bs.getResult(0, ary));
  assertEquals(false, bs.getResult(-1, ary));
  ary = new int[2];
  ary[0] = 0;
  ary[1] = 4;
  // 2개짜리 배열에 0,4가 들어가 있을때
  assertEquals(false, bs.getResult(-1, ary));
  assertEquals(true, bs.getResult(0, ary));
  assertEquals(false, bs.getResult(1, ary));
  assertEquals(false, bs.getResult(2, ary));
  assertEquals(false, bs.getResult(3, ary));
  assertEquals(true, bs.getResult(4, ary));
  assertEquals(false, bs.getResult(5, ary));
 }

2글짜 배열에 대하여는 처리하는 코드가 없으므로 테스트는 실패한다.


통과하는 테스트 코드 작성하기

각 입력 케이스마다 통과하도록 result의 값을 하드코딩한다.

  public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  if (ary.length == 2) {
   if (searchValue == -1) {
    result = false;
   }
   if (searchValue == 0) {
    result = true;
   }
   if (searchValue == 1) {
    result = false;
   }
   if (searchValue == 2) {
    result = false;
   }
   if (searchValue == 3) {
    result = false;
   }
   if (searchValue == 4) {
    result = true;
   }
   if (searchValue == 5) {
    result = false;
   }
  } else if (ary.length == 1) {
   if (searchValue == ary[0])
    result = true;
   else {
    result = false;
   }
  } else {
   if (searchValue == 47) {
    result = true;
   }
  }
  return result;
 }

테스트는 통과한다.

리팩토링

각 입력값에는 아래와 같은 절차가 포함된다.

  public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  if (ary.length == 2) {
   if (searchValue == -1) {
    if (ary[0] == searchValue) {
     result = true;
    } else if (ary[1] == searchValue) {
     result = true;
    } else {
     result = false;
    }
   }
   if (searchValue == 0) {
    if (ary[0] == searchValue) {
     result = true;
    } else if (ary[1] == searchValue) {
     result = true;
    } else {
     result = false;
    }
   }
   if (searchValue == 1) {
    if (ary[0] == searchValue) {
     result = true;
    } else if (ary[1] == searchValue) {
     result = true;
    } else {
     result = false;
    }
   }
   if (searchValue == 2) {
    if (ary[0] == searchValue) {
     result = true;
    } else if (ary[1] == searchValue) {
     result = true;
    } else {
     result = false;
    }
   }
   if (searchValue == 3) {
    if (ary[0] == searchValue) {
     result = true;
    } else if (ary[1] == searchValue) {
     result = true;
    } else {
     result = false;
    }
   }
   if (searchValue == 4) {
    if (ary[0] == searchValue) {
     result = true;
    } else if (ary[1] == searchValue) {
     result = true;
    } else {
     result = false;
    }
   }
   if (searchValue == 5) {
    if (ary[0] == searchValue) {
     result = true;
    } else if (ary[1] == searchValue) {
     result = true;
    } else {
     result = false;
    }
   }
  } else if (ary.length == 1) {
   if (searchValue == ary[0])
    result = true;
   else {
    result = false;
   }
  } else {
   if (searchValue == 47) {
    result = false;
   }
  }
  return result;
 }

리팩토링

-1~5의 경우 각 케이스마다 처리 내용이 완전히 중복되므로 바깥쪽 if문을 없애고, 중복을 제거하면 다음과 같다.

  public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  if (ary.length == 2) {
   if (ary[0] == searchValue) {
    result = true;
   } else if (ary[1] == searchValue) {
    result = true;
   } else {
    result = false;
   }
  } else if (ary.length == 1) {
   if (searchValue == ary[0])
    result = true;
   else {
    result = false;
   }
  } else {
   if (searchValue == 47) {
    result = false;
   }
  }
  return result;
 }

코드 커밋하기


네번째 TDD Cycle

실패하는 테스트 코드 만들기

세개의 배열의 테스트를 진행한다.

   // 3개짜리 배열에 2,3,7가 들어가 있을때
  ary = new int[3];
  ary[0] = 2;
  ary[1] = 3;
  ary[2] = 7;
  assertEquals(false, bs.getResult(-1, ary));
  assertEquals(false, bs.getResult(1, ary));
  assertEquals(true, bs.getResult(3, ary));
  assertEquals(false, bs.getResult(4, ary));
  assertEquals(true, bs.getResult(2, ary));
  assertEquals(true, bs.getResult(7, ary));

배열의 3개일 경우에 처리방법을 기술하지 않았으므로 테스트는 실패한다.

테스트 코드 통과시키기

배열의 2개일 경우의 처리방법에 아래의 문장을 추가시키고 사용했더니 통과했다.

else if (ary[2] == searchValue) 
{
       result = true;
}

이제 아래의 경우에 중복을 볼 수 있다.

  public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  if (ary.length == 3) {
   if (ary[0] == searchValue) {
    result = true;
   } else if (ary[1] == searchValue) {
    result = true;
   } else if (ary[2] == searchValue) {
    result = true;
   } else {
    result = false;
   }
  } else if (ary.length == 2) {
   if (ary[0] == searchValue) {
    result = true;
   } else if (ary[1] == searchValue) {
    result = true;
   } else {
    result = false;
   }
  } else if (ary.length == 1) {
   if (searchValue == ary[0])
    result = true;
   else {
    result = false;
   }
  } else {
   if (searchValue == 47) {
    result = true;
   }
  }
  return result;
 }

리팩토링

배열이 3개일 경우에 값 탐색 코드

   if (ary.length == 3) {
   if (ary[0] == searchValue) {
    result = true;
   } else if (ary[1] == searchValue) {
    result = true;
   } else if (ary[2] == searchValue) {
    result = true;
   } else {
    result = false;
   }
  }

중복을 제거한 코드 (result의 기본값이 false이므로 if문 밖으로 뺄 수 있다.)

 if (ary.length == 3) {
   for (int i = 0; i < ary.length; i++) {
    if (ary[i] == searchValue) {
     result = true;
    }
   }
  }


리팩토링

나머지 배열 2개, 배열 1개에도 동일하게 적용하여 중복을 제거한다.

  public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  for (int i = 0; i < ary.length; i++) {
   if (ary[i] == searchValue) {
    result = true;
   }
  }
  return result;
 }

리팩토링

배열이 오름차순이라는 조건이 있으므로, 탐색하는 배열의 값은 갈수록 커지게 된다.

만일 현재 배열의 값이 찾고자 하는 값보다 크다면 , 앞으로 탐색할 값은 계속 커질것이기 때문에 더이상의 탐색은 무의미하다.

따라서 아래와 같은 조건문을 추가해준다.

  public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  for (int i = 0; i < ary.length; i++) {
   if (ary[i] > searchValue) {
    break;
   }
   if (ary[i] == searchValue) {
    result = true;
   }
  }
  return result;
 }

코드 커밋하기


이로써, 탐색 알고리즘은 완성이 되었다.

하지만 이는 이진 탐색이 아닌, 순차 탐색의 알고리즘이다.

문제의 요구사항은 이진 탐색이므로 탐색 알고리즘을 다시 작성한다.

이진 탐색을 하려면 배열의 개수가 적다면 이진 탐색의 과정을 하드코딩으로 작업하는 과정이 어렵다.

따라서 20개정도의 배열에서 이진트리의 과정을 작업하기로 한다.

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39가 들어있는 20개의 배열에서 값들을 검색하는 테스트 코드를 추가한다.

또한 이 테스트코드를 위하여 배열의 값이 20개일때, 따로 기능을 처리하도록 프로덕션 코드에 if 분기문을 추가한다.

  public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  if (ary.length == 20) {
  } else {
   for (int i = 0; i < ary.length; i++) {
    if (ary[i] > searchValue) {
     break;
    }
    if (ary[i] == searchValue) {
     result = true;
    }
   }
  }
  return result;
 }

다섯번째 TDD Cycle

실패하는 테스트 코드 작성하기

값이 10개일때 기능을 처리하는 조건문이 없으므로 테스트 케이스는 실패한다.

  ary = new int[20];
  int cnt = 1;
  for (int i = 0; i < 20; i++) {
   ary[i] = cnt;
   cnt += 2;
  }
  assertEquals(true, bs.getResult(13, ary));

통과하는 테스트 코드 만들기

탐색값 13이 들어오면 결과값을 true로 반환하도록 한다

  public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  if (ary.length == 20) {
   if(searchValue == 13)
   {
    result = true;
   }
  } else {
   for (int i = 0; i < ary.length; i++) {
    if (ary[i] > searchValue) {
     break;
    }
    if (ary[i] == searchValue) {
     result = true;
    }
   }
  }
  return result;
 }

리팩토링

없다.

코드 커밋하기


실패하는 테스트 코드 만들기

13일때만 처리가 가능하도록 만들었으므로 9가 들어가면 테스트코드는 실패한다.

assertEquals(true, bs.getResult(13, ary));
assertEquals(true, bs.getResult(29, ary)); //실패

테스트 코드 통과시키기

마찬가지로 탐색값 29가 들어왔을때 결과값에 true를 반환시키도록 설정

public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  if (ary.length == 20) {
   if (searchValue == 13) {
    result = true;
   }
   if (searchValue == 29) {
    result = true;
   }
  } else {
   for (int i = 0; i < ary.length; i++) {
    if (ary[i] > searchValue) {
     break;
    }
    if (ary[i] == searchValue) {
     result = true;
    }
   }
  }
  return result;
 }

리팩토링

13은 배열의 6번째 요소

9는 배열의 14번째 요소에 있다.

if (ary.length == 20) {
   if (searchValue == 13) {
    if (searchValue == ary[6]) {
     result = true;
    }
   }
   if (searchValue == 29) {
    if (searchValue == ary[14]) {
     result = true;
    }
   }
  }

리팩토링

아래와 같은 비교 과정을 거친다.

  public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  if (ary.length == 20) {
   if (searchValue == 13) {
    if (searchValue != ary[10]) {
     if (searchValue != ary[5]) {
      if (searchValue != ary[7]) {
       if (searchValue == ary[6]) {
        result = true;
       }
      }
     }
    }
   }
   if (searchValue == 29) {
    if (searchValue != ary[10]) {
     if (searchValue != ary[15]) {
      if (searchValue == ary[14]) {
       result = true;
      }
     }
    }
   }
  }

리팩토링

비교 배열을 index라는 이름으로 명명

  public boolean getResult(int searchValue, int[] ary) {
  boolean result = false;
  if (ary.length == 20) {
   if (searchValue == 13) {
    int index = 10;
    if (searchValue != ary[index]) {
     index = 5;
     if (searchValue != ary[index]) {
      index = 7;
      if (searchValue != ary[index]) {
       index = 6;
       if (searchValue == ary[index]) {
        result = true;
       }
      }
     }
    }
   }
   if (searchValue == 29) {
    int index = 10;
    if (searchValue != ary[index]) {
     index = 15;
     if (searchValue != ary[index]) {
      index = 14;
      if (searchValue == ary[index]) {
       result = true;
      }
     }
    }
   }
  }


13의 경우를 보면

10 5 7 6 의 인덱스가 비교되고

29일 경우를 보면

10 15 13 14의 인덱스가 비교된다.

이를 잘 살펴보면 어떤 규칙이 있다.

증감되는 절대값이 5, 2, 1로 똑같다는 것이다.

5, 2, 1은 전 값의 1/2라는 공통점이 있다.

리팩토링

절대값을 의미하는 abs라는 변수명을 넣고, 1/2씩 감소시킨다.

 if (searchValue == 13) {
    int index = 10;
    int abs = 5;
    if (searchValue != ary[index]) {
     index -= abs; // -5
     abs /= 2;
     if (searchValue != ary[index]) {
      index += abs; // +2
      abs /= 2;
      if (searchValue != ary[index]) {
       index = 6; // +1
       abs /= 2;
       if (searchValue == ary[index]) {
        result = true;
       }
      }
     }
    }
   }
   if (searchValue == 29) {
    int index = 10;
    int abs = 5;
    if (searchValue != ary[index]) {
     index += abs;
     abs /= 2;
     if (searchValue != ary[index]) {
      index -= abs; // -2
      abs /= 2;
      if (searchValue != ary[index]) {
       index += abs; // +1
       abs /= 2;
       if (searchValue == ary[index]) {
        result = true;
       }
      }
     }
    }
   }

그러면 어떤 경우는 절대값을 빼주고

어떤 경우는 절대값을 더해주는 것일까?

탐색 값이 현재 값보다 작으면 절대값을 빼주고 (탐색 기준 인덱스를 앞으로 이동)

탐색 값이 현재 값보다 크면 절대값을 더해준다 (탐색 기준 인덱스를 뒤로 이동)

리팩토링

현재 값을 기준으로 절대값을 더하거나 빼는 조건문을 추가시킨다.

 if (ary.length == 20) {
   if (searchValue == 13) {
    int index = 10;
    int abs = 5;
    if (searchValue != ary[index]) {
     if (searchValue > ary[index])
      index += abs; // -5
     else
      index -= abs;
     abs /= 2;
     if (searchValue != ary[index]) {
      if (searchValue > ary[index])
       index += abs; // +2
      else
       index -= abs;
      abs /= 2;
      if (searchValue != ary[index]) {
       if (searchValue > ary[index])
        index += abs; // -1
       else
        index -= abs;
       abs /= 2;
       if (searchValue == ary[index]) {
        result = true;
       }
      }
     }
    }
   }
   if (searchValue == 29) {
    int index = 10;
    int abs = 5;
    if (searchValue != ary[index]) {
     if (searchValue > ary[index])
      index += abs;
     else
      index -= abs;
     abs /= 2;
     if (searchValue != ary[index]) {
      if (searchValue > ary[index])
       index += abs; // -2
      else
       index -= abs;
      abs /= 2;
      if (searchValue != ary[index]) {
       if (searchValue > ary[index])
        index += abs; // +1
       else
        index -= abs;
       abs /= 2;
       if (searchValue == ary[index]) {
        result = true;
       }
      }
     }
    }
   }

이제 13과 29에서 중복이 상당히 많아졌음을 볼 수 있다.

리팩토링

찾는 값과 현재 값이 같으면 결과값에 true를 넣는 부분은 어느 검사 단계에서나 같으므로 아래 구문을 각 단계에 추가시켜준다.

if (searchValue == ary[index]) {
result = true;
}

 if (ary.length == 20) {
   if (searchValue == 13) {
    int index = 10;
    int abs = 5;
    if (searchValue != ary[index]) {
     if (searchValue == ary[index]) {
      result = true;
     }
     if (searchValue > ary[index])
      index += abs; // -5
     else
      index -= abs;
     abs /= 2;
     if (searchValue != ary[index]) {
      if (searchValue == ary[index]) {
       result = true;
      }
      if (searchValue > ary[index])
       index += abs; // +2
      else
       index -= abs;
      abs /= 2;
      if (searchValue != ary[index]) {
       if (searchValue == ary[index]) {
        result = true;
       }
       if (searchValue > ary[index])
        index += abs; // -1
       else
        index -= abs;
       abs /= 2;
       if (searchValue == ary[index]) {
        result = true;
       }
      }
     }
    }
   }
   if (searchValue == 29) {
    int index = 10;
    int abs = 5;
    if (searchValue != ary[index]) {
     if (searchValue == ary[index]) {
      result = true;
     }
     if (searchValue > ary[index])
      index += abs;
     else
      index -= abs;
     abs /= 2;
     if (searchValue != ary[index]) {
      if (searchValue == ary[index]) {
       result = true;
      }
      if (searchValue > ary[index])
       index += abs; // -2
      else
       index -= abs;
      abs /= 2;
      if (searchValue != ary[index]) {
       if (searchValue == ary[index]) {
        result = true;
       }
       if (searchValue > ary[index])
        index += abs; // +1
       else
        index -= abs;
       abs /= 2;
       if (searchValue == ary[index]) {
        result = true;
       }
      }
     }
    }
   }
  }

리팩토링

13과 29일 경우 조건문 내용이 동일해졌으므로 통합해준다

 if (ary.length == 20) {
   int index = 10;
   int abs = 5;
   if (searchValue != ary[index]) {
    if (searchValue == ary[index]) {
     result = true;
    }
    if (searchValue > ary[index])
     index += abs; // -5
    else
     index -= abs;
    abs /= 2;
    if (searchValue != ary[index]) {
     if (searchValue == ary[index]) {
      result = true;
     }
     if (searchValue > ary[index])
      index += abs; // +2
     else
      index -= abs;
     abs /= 2;
     if (searchValue != ary[index]) {
      if (searchValue == ary[index]) {
       result = true;
      }
      if (searchValue > ary[index])
       index += abs; // -1
      else
       index -= abs;
      abs /= 2;
      if (searchValue == ary[index]) {
       result = true;
      }
     }
    }
   }
  }

리팩토링

중첩된 if문들이 중복되는 부분이 계속해서 반복된다.

반복문을 사용하여 간소화 시켜 준다.

 if (ary.length == 20) {
   int index = ary.length / 2;
   int abs = index / 2;
   for (int i = 0; i < 4; i++) {
    if (searchValue == ary[index]) {
     result = true;
    }
    if (searchValue > ary[index]) {
     index += abs; // -5
    } else
     index -= abs;
    abs /= 2;
   }
  }

리팩토링

이진탐색은 배열의 처음과 끝의 탐색 범위를 지정하고 그 가운데 인덱스 요소를 검사 대상으로 삼는다.

따라서 검사 대상인 ary[index]를 mid로 명명한다.

 if (ary.length == 20) {
   int index = ary.length / 2;
   int abs = index / 2;
   int mid = ary[index];
   for (int i = 0; i < 4; i++) {
    if (searchValue == mid) {
     result = true;
    }
    if (searchValue > mid) {
     index += abs;
    } else
     index -= abs;
    mid = ary[index];
    abs /= 2;
   }
  }


리팩토링

기존에 4번 반복하는 반복문에서

결과를 발견하면 반복문을 종료하도록 수정했다.

 if (ary.length == 20) {
   int index = ary.length / 2;
   int abs = index / 2;
   int mid = ary[index];
   while (!result) {
    if (searchValue == mid) {
     result = true;
    }
    if (searchValue > mid) {
     index += abs;
    } else
     index -= abs;
    mid = ary[index];
    abs /= 2;
   }
  }


코드 커밋하기


일반화 테스트

내가 만든 코드가 일반화된 솔루션인지 테스트하기 위해 여러가지 값을 넣어서 테스트해봤다.

  assertEquals(true, bs.getResult(13, ary)); //성공
  assertEquals(true, bs.getResult(29, ary)); //성공
  assertEquals(true, bs.getResult(35, ary)); //성공
  assertEquals(true, bs.getResult(13, ary)); //성공
  assertEquals(true, bs.getResult(23, ary)); // 무한반복
  assertEquals(true, bs.getResult(39, ary)); // 무한반복


아래 2개의 값은 무한루프에 빠져버렸다. 

왜 이렇게 됬을까?

인덱스에 더해지는 절대값은 절반씩 줄어든다.

23의 경우 인덱스 11에 위치해 있다.

인덱스 11을 탐색하기 위한 과정은 아래와 같다.

10 (+5) 

15 (-2)

13 (-1)

12 (-0)

12에서 절대값은 0이 되버리기 때문에 인덱스 11에 도달할 수 없고, 따라서 while문이 무한 반복되는 것이다.

이 문제를 해결하려면 어떻게 해야 할까?

....

생각해보니 절대값을 줄여서 빼면 분명 허점이 생긴다.

극단적으로 찾는 값이 맨 앞이나 맨 뒤에 있는 경우를 보자.

찾는 값이 0번째 인덱스에 있다면 어떻게 찾을 것인가

10->5->3->2 (0, 1 탐색불가)

찾는 값이 19번째 인덱스에 있다면 어떻게 찾을 것인가.

10 -> 15 -> 17 -> 18 (19 탐색불가)


최악의 경우를 기준으로 두고 생각해보자.

찾는 값이 맨 앞에 있는 경우..


TDD를 이용한 2진 탐색 3번째


오이사님과 2진 탐색을 새로 만들었다.

실패한 이유는 내가 무엇을 테스트하는지 방향이 틀려서이다.


2번째 시도(위)에서 이런 코드가 있었다.

이런 코드가 굳이 필요할까?


public boolean getResult(int searchValue, int[] ary) {
    boolean result = false;
    if (ary.length == 2) {
        if (searchValue == -1) {
            result = false;
        }
        if (searchValue == 0) {
            result = true;
        }
        if (searchValue == 1) {
            result = false;
        }
        if (searchValue == 2) {
            result = false;
        }
        if (searchValue == 3) {
            result = false;
        }
        if (searchValue == 4) {
            result = true;
        }
        if (searchValue == 5) {
            result = false;
        }
    } else if (ary.length == 1) {
        if (searchValue == ary[0])
            result = true;
        else {
            result = false;
        }
    } else {
        if (searchValue == 47) {
            result = true;
        }
    }
    return result;
}


그렇지 않다. 이미 틀리는 코드를 작성했는데 왜 또 작성하는가?

처음에 SoundEX를 생각해서 틀리는 케이스를 여러가지 작성한다음에 공통점을 추출하려고 했었다.

하지만 SoundEX와 2진탐색은 속성이 다르다. 

SoundEX는 문자열에 따라 결과값이 무한하다. (따라서, 여러가지 테스트 케이스를 넣어도 됬었다.)

하지만 2진탐색은 입력값에 따라 결과값이 true, false두가지밖에 나오지 않는다.

따라서 2진탐색의 경우 틀리는 수만가지 값을 입력한다고 해도 의미있는 행동이 아니다.

테스트하는 목적을 명확하게 정하는 것이 옳다.

false를 반환하는 경우

  1. 탐색을 했지만 찾는 값이 없는 경우
  2. 애초에 값을 비교할 필요 없는 경우
    1. 배열의 크기가 0이다.
    2. 탐색값이 배열의 최소값보다 작다.
    3. 탐색값이 배열의 최대값보다 크다.

이때 '경계값'이라는 개념이 나온다.

만약에 0을 검사한다면, 탐색값보다 작은 값은 -1이 될 것이다. 그 이하로 -2, -3등은 비교할 필요가 없다. (이미 작은 값을 검사하는 코드를 작성했으므로)

탐색값보다 큰 값은 1이 될 것이다.

이렇게 틀리는 최소 조건을 가진 값을 '경계값'이라고 하는 것 같다.

두번째는 굳이 result에 값을 저장해서 반환할 필요가 없다는 것이다.

result에 true, false를 넣어서 반환하려고 했기 때문에 로직이 복잡해졌다.

return true, false를 썼었다면 굳이 if문 안의 if문을 반복하지 않았어도 됬었다.

중요한것은 output의 형태이지, 꼭 result에 넣어서 반환하는 형식을 지키지는 않아도 되는 것 같다. (지키면 가독성이 좀 좋겠지만, 잃어야 되는 것이 너무 많다면 굳이 지킬 필요는 없다는 말)

세번째는 이미 알고리즘을 알고있는 가정이라면, 시작부터 10개정도의 배열로 테스트해서 하드코딩 -> 일반화의 과정을 거치는 것도 좋다.

TDD라고 무조건적으로 코딩부터 하고 테스트를 반복하는 것이 아니다.

프로그램을 짜기 전에 내가 어떤 방향으로 짤 것인지를 명확하게 해야 중간에 방향을 잃는 일이 없을 것이다.


 

'IT > 프로그래밍' 카테고리의 다른 글

Bit 연산 Leaning Test  (0) 2015.12.06
[TDD] 시침과 분침 사이 각도 계산  (0) 2015.12.06
웹 프로토콜 동작 원리  (0) 2015.12.06
URL 구조 분석  (0) 2015.12.06
Spring 기본 세팅, 기본 출력, doPost, doGet메소드  (0) 2015.12.01

관련글 더보기

댓글 영역

티스토리툴바