wnsrnek3   3년 전

충분히 빠르게 binary Search로 구현한거같은데...

예시 결과는 잘나오는데 왜 시간초과가 뜰까요...







(ubuntu linux상에서 해서 배열크기 const아닌 int로 동적으로 잡은건 신경안쓰셔도 될것같습니다...)

wondy1128   3년 전

binSch 안에 루프(1) 에서 나올 수 있는 조건이 부족하지 않나 생각해봅니다.

// 0 1 2 3 4 5 6 7 8 9

인 조건에서 찾을 값이 우측에 편향되어 있거나 , 사이 값인 경우에

// min mid max

// 0 4 9

// 4 6 9

// 6 7 9

// 7 8 9

// 8 8 9

// 8 8 9

// 8 8 9

... 계속 8 8 9 인 상태가 되어서 루프를 종료하지 못하고 돌 것 같습니다.

wondy1128   3년 전

코드를 돌려본 결과 16-20 줄 라인에 교체는 값인 r , l  = ( ) ; 여기를 수정하고, 종료조건 하나를 넣어주면 될 것 같네요. 인덱스 조건을 벗어난 경우에 
수정하여 돌려보니 맞았다고 결과를 보여주네요

wnsrnek3   3년 전

감사합니다!

if (arr[l]<v && v<arr[m]) {     // left
r=m-1;
}else if(arr[m]<v && v<arr[r]){ //right
l=m+1;
}else{ printf("0\n");break;}


m은 더이상 볼필요가 없었네요... m-1, m+1로 각각 바꾸어주니 제대로 동작합니다! 감사합니다!!!! ㄷㅇㄴㅎ ㅅㄹㅎㄴㄷ

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