[일반] 이분탐색할 때 mid값 조정하는 거 짬이 해결함?

[익명(175.196)]

어쩔 땐 (st + en) / 2, 또 어쩔 땐 (st + en + 1) / 2 여야 무한루프 안빠지고 참...

[익명(14.33)]

s + (e - s) / 2 해서 무한루프 빠진 적이 없는데

[ㅁ(141.223)]

[L,R] 구간을 둘로 자를때 무조건 [L,mid-1],[mid+1,R]로 나누셈. 그러면 뭐로 잡든 무한루프 안빠짐. 이분탐색 하고나서 절대 mid를 다시 구간에 넣지 마. 그게 만악의 근원임

[익명(175.196)]

오오 ㄳㄳ 그러면 ans라는 변수를 밖에 빼놓고 이분 탐색 안에서 성공했을 때만 ans = mid 해놓고 st = mid + 1 or en = mid - 1 해주는 게 좋은 거네. 진짜 고맙다

[ㅁ(141.223)]

ㅇㅇ 배열위에서 이분탐색은 무조건 이방법이 좋음. 그 이외의 방법은 전부 구현 잘못하면 무한루프 날수있는 안좋은 코드임(특히 인터넷에 있는 이분탐색 코드 대부분)

[ㅁ(141.223)]

인터넷에서 이분탐색할때 이런식으로 소개하는 이유가 배열위에서 이분탐색 말고 실수구간 위에서 이분탐색할때도 사용가능해서 그런데, PS에서 실수구간 위에서 이분탐색할때 저렇게 코딩 안함. 다 while문 몇번도는지 최대값 정해서 하지.

[익명(175.196)]

파라메트릭 서치도 글케 많이 하던데 일단 ㅇㅋ. 마지막으로 while (st < en) or while (st <= en) 이거 둘 중 어떨 때 쓰는 거임?

[익명(175.196)]

으으 실수구간은 좀 어렵겠네

[ㅁ(141.223)]

케바케임. 구간을 [a,b) 형태로 반구간으로 보는 사람도 있고 [a,b] 형태의 닫힌구간으로 보는 사람도 있음. 첫번째는 컴공에서 좋아하는 방식이고 두번째는 사람들이 자주 사용하는 직관적인 방식임. 전자면 st

[익명(175.196)]

전자면 st?

[ㅁ(141.223)]

디시 코딩 누가 이따구로했냐 전자면 st 가 en보다 작게 쓰고 수자면 st가 en보다 같거나 작다고 씀

[익명(175.196)]

너는 어느 걸 선호해?

[ㅁ(141.223)]

난 후자. 무조건 직관적인 코딩을 선호함. 0으로 시작하고 반구간으로 적는건 컴퓨터 성능이 후질때나 나온 전통이지 굳이 컴퓨터에 맞추려고 내 코딩 비직관적으로 적고싶지 않아서. 무조건 배열은 1부터 시작, 닫힌 구간으로 적음

[익명(175.196)]

예를 들어서 [1, 2, 3, 4, 5] 에서 4를 찾는다면 st = 0, en = 4, while (st <= en) 을 쓴다는 거임? 전자 방식은 st = 0, en = 5, while (st < en) 이거고?

[ㅁ(141.223)]

ㅇㅇ 정확히 그럼. 후자는 그러면 구간을 [st,en)형식이니 mid 빼면 구간이 [st,mid)와 [mid+1,en)형식으로 나눠지겠지. 조금 헷갈리긴 한데 무조건 mid를 빼는 형식으로 구간을 나눈다 생각하면 이해하기 쉬움

[익명(175.196)]

후자는 [st, en] 형식 아님?? [st, en)은 전자 ( while (st < en) ) 이거고

[ㅁ(141.223)]

아 그러네 ㅇㅇ 너말 맞음

[익명(175.196)]

무조건 mid를 빼는 형식으로 구간을 나눈다는 의미 좀더 상세히 설명 가능?

[ㅁ(141.223)]

이미 설명할대로 설명한것 같은데. 나도 갤질만 하고있을 수 없고 바빠서 나머지는 다른 갤럼이 설명해줄거야 미안

[익명(175.196)]

아 그래 미안 ㅋㅋ 고마워

[익명(218.239)]

그냥 템플릿을 통째로 외우면 딱히 짬으로 뭐 바꿀 필요 없음 [s, e]에서 이분탐색을 한다고 하고 이분탐색을 할 조건을 binary_search(), binary_search(e)가 참일 때 int s, e; while(s!=e) { int mid=(s+e)/2; if(binary_search(mid)) e=mid; else s=mid+1; } 을 하면 [s, e]에서 binary_search가 참인 가장 작은 값이 변수 s와 e에 저장되어있음

[익명(175.196)]

운동갔다 오니까 댓글 많이 달렸네. ㄳㄳ

[익명(175.115)]

https://www.acmicpc.net/blog/view/109

[익명(180.70)]

이게 최고임

[익명(175.196)]

ㄳㄳ

[익명(121.131)]

bool반환하는 어떤 함수 f가 있고 f(x)값이 x가 증가함에 따라 TTTTTFFFFF 처럼 나타나는게 단조성이 있는거지? 보통 T에서 F로 바뀌는 부분에 관심이 있고 그러면 s,e를 적당히 잡고 while s+1 < e로 잡고 함 s=mid나 e=mid로 갱신하고 그러면 바뀌는 부분이 s e로 나옴

[익명(175.196)]

방법이 많구나

[캐티(tae826)]

이게 어차피 무한루프가 도는 경우는 처음 l 또는 처음 r 로 가는 경우라서 둘 중 하나로 갔을때 무한루프가 뜨는지 안 뜨는지만 생각해서 (s+e)/2 랑 (s+e+1)/2 랑 구별하면 되긴 함

[캐티(tae826)]

위에 언급된거처럼 l, mid-1 / mid / mid+1, r 로 하는 것도 방법이고

[익명(175.196)]

ans 변수를 따로 두는 게 맘 편하긴 함