harry1992   4년 전

안녕하세요 일단 문제는 맞췄는데요

항상 binarySearch를 recursive로 짤때 보면

binarSearch(int* arr, int start, int end)

에서

start>end 가 되면 return 시켜주는 코드가 있던데 이게 start , end의 index 가 올바로 입력되었을때도 함수 파고 들어가다 보면

start>end가 되는 case가 생기나요?? 혹시 생긴다면 예를 좀 들어주시면 감사하겠습니다.

제 돌대가리로는 아무리 돌려도 start==end 케이스까지 밖에 생각이 나지 않아서.. 고수분들 댓글 달아주시면 감사하겠습니다!!





chogahui05   4년 전

없을 리가요. ㅎㅎ

5 7 8 11 14 16에서 13을 찾는다고 해 봅시다.

일단 처음에 left = 0, right = 5였습니다. mid는 2네요.

arr[mid] = 8입니다. 8은 13보다는 작으므로 우측에서 찾아야겠죠.


따라서 left = 3, right = 5네요.

여기서 mid 값은 4네요. arr[mid] = 14 > 13이네요? 중간이 내가 찾으려는 것보단 크므로

right = mid - 1 = 3이 됩니다.


이제 left = 3, right = 3입니다.

자.. arr[mid] = 11입니다. 11 < 13이지요? 당연한 이야기겠지만.


중간값이 내가 찾으려는 것보다 작은 경우에는 우측에서 찾아야 겠네요.

고로 left = 4가 되는데요.


여기서 4<3이 됩니다. left가 오히려 right보다 크죠.

천천히 그려보세요. 정 이해가 안 되시면 직접 디버깅 해 보세요.

djm03178   4년 전

그 부분이 있는 덕분에, if (start == end) { 부분은 통째로 필요가 없지 않나 싶네요. start == end라면, 따로 조건 검사를 하지 않아도 mid == start가 되므로, 그 자리에 있는지 여부는 검사할 수 있으니까요. 만약 아니라고 판명났다면, 어느 쪽에서 재귀호출이 되든 start > end에 걸려서 없다는 것이 확정되고 탐색이 종료될 거고요.

chogahui05   4년 전

엇? 중간에 start == end가 있었네요.. 아놔..

오늘 새벽에 밤샘해서 정신이 없었나 보네요.. 근데 코드 대충 보니 start == end 빼셔도 맞으실 거에요.

harry1992   4년 전

두분 다 감사드립니다. 쉽게 이해 됐어요 감사드립니다!!

harry1992   4년 전

그럼 제가 썼떤 start==end 부분이 있으면 start>end 가 되는 경우는 안나오는게 맞는걸까요??

chogahui05   4년 전

아. start==end만 있으면 런타임 에러가 나는 예 찾았습니다!!

djm03178   4년 전

있을 수도 있지 않을까요? 가령, 1 2 4 5에서 3을 찾는다고 하면,

start = 0, end = 3, mid = 1에서 2보다 3이 크므로 오른쪽을 찾고,

start = 2, end = 3, mid = 2에서 4보다 3이 작으므로 왼쪽을 찾아야 되는데, 이 때 호출되는 게 start = 2이고 end = 1이죠.

harry1992   4년 전

와 감사합니다.. chogahui05 님 djm03178 님 .. 배우고 갑니다..

댓글을 작성하려면 로그인해야 합니다.