토크:이진 검색 알고리즘
 | show 기타 토크 페이지 배너 |
|---|
기본 절차가 "실패한" 사례에서 위치를 양보할 수 있음
2단계에서 검색이 "실패"로 종료되면 목표값 'T'가 A와R A 사이에L 위치하게 될 것이라고 본다. 즉, R은 T보다 작은 배열 요소의 색인(대략 -1)이고 L은 T보다 큰 배열 요소의 배열 요소 색인(대략 n)이다.
나는 이 절차의 속성이 범위를 검색할 때 유용하다는 것을 알았다. 내 생각에 그것은 평균적으로 가장 오른쪽 혹은 가장 왼쪽의 변형을 사용하는 것보다 한 발 더 빠를 것이다.
기사 페이지에 있는 노트가 정당한지는 잘 모르겠지만, 이 정보를 가지고 있는 것이 "범위" 검색을 하는 사람들에게 도움이 될 것이다. 기사 페이지에 있는 노트가 WRT가 인용한 작업 대 원본 작업, 다른 토크 주제를 위반하는 것일 수도 있다.
이것은 가장 왼쪽 또는 가장 오른쪽 변형의 효용성에 대한 언급이 아니다. 배열에 중복 항목이 포함될 수 있을 때 유용하다. 일반적으로 값이 어느 범위에 있는지 결정하는 것이 문제인 경우에는 중복 항목이 존재하지 않는다.
글렌프17321 (대화) 18:52, 2020년 5월 17일 (UTC)[]
범위에는 배타적 상한이 있어야 함
나는 대학교 수준에서 바이너리 검색을 여러 번 가르쳤다. CS에서 마스터스를 가진 사람들로부터 인터뷰 질문으로 50번 정도 물어본 적도 있다. 나는 사람들이 내 인터뷰 질문에 실패하는 주된 이유는 바이너리 검색이 배타적인 것이 아니라 일반적으로 포괄적 상한을 가지고 가르쳐지기 때문이라고 판단했다. 이 위키백과 기사는 그 습관을 계속한다. 나는 그 기사가 독점적인 상한선으로 전환됨으로써 실질적으로 개선될 것이라고 생각한다.
"배타적 상한"이라는 말은, {\} 요소 배열의 초기 가 R=n ={\L= R = {\R이 된다는 뜻 내가 본 거의 모든 양호한 배열 코드는 배타적 상한을 사용한다. Java의 모든 라이브러리는 독점적인 상한을 사용한다. 배타적 상한의 한 가지 좋은 속성은 - L 이(가) 항목 수라는 것이다. 유의점은 = 이(가) 빈 범위에 대한 이고 < R 은(는) 비어 있지 않은 범위에 대한 테스트라는 것이다. Another good property of exclusive upper bounds is that for any where ≤≤, it is easy to split the range into two subranges and . These properties make reasoning 암호에 대해 훨씬 더 쉽게 이야기하다.
된다는 뜻
(가) 항목 수라는 것이다. 유의점은 
(는) 비어 있지 않은 범위에 대한 테스트라는 것이다. Another good property of exclusive upper bounds is that for any 
배타적 상한을 사용할 경우 이진 검색에 대한 코드는 매우 자연스러워진다.
function binary_search_exclusive_upper_bound(A, n, T) is L := 0 R := n while R-L ≥ 2 do m := L + floor((R-L)/ 2) if T < A[m] then R := m else: L := m if R-L=1 and A[L] = T then return L return unsuccessful
Nota Bene: 나는 "and" 운영자가 단락 평가를 사용한다고 가정한다.
위 코드를 메인 페이지의 코드와 비교하십시오. 나는 네가 이 코드를 이해하기가 훨씬 쉽다는 것을 알았으면 좋겠어. You can see that (1) the loop runs only when it can split the range, (2) that is clearly not equal to and not equal to , (3) that it doesn't matter if I used or to compute (4) 범위 변수가 1회 오류 없이 올바르게 처리되며 (5) 이(가) 0인 경우와 같이 모든 경우를 코드가 처리한다.
BTW, 는 n 을(를) 취급하는 것이 빈 범위인 0이라고 생각한다. 메인 페이지에 인용된 패티스의 논문도 이를 중요하게 여긴다. 메인 의" 버전은 n {\displaystyle n}이(가) 0이면 무한 루프에 들어간다. 나는 그것을 비독점적 상한을 사용한 결과로 본다. 왜냐하면 메인 페이지의 코드는 이해하기 어렵기 때문이다.
나는 바이너리 검색이 너무 오래된 알고리즘이기 때문에 일반적으로 포괄적 상한을 가지고 가르쳐진다고 믿는다. 그것이 만들어졌을 때, 우리는 (80년대 초반에 C와 함께 배운) 배타적 상한을 사용하는 습관이 없었다. 그러나 거의 모든 어레이 코드는 현재 배타적 상한을 사용한다. 배타적 상한을 사용하는 것은 설득하기가 더 쉽다. 나는 이 기사가 독점적인 상한을 사용함으로써 실질적으로 개선될 것이라고 굳게 믿는다.
마이클 나하스, 전 버지니아 대학 부속 교수, 전 존스 홉킨스 영재센터 강사
P.S. 외부 참조가 필요하면 내 웹사이트에 내 의견을 적었다.
Mdnahas (대화) 23:07, 2021년 6월 17일 (UTC)[]
- 의견을 공유해주셔서 정말 감사하다! 나는 배타적 하한선이 이 알고리즘에 대해 더 좋고 논리적인 구현 방법이라는 것에 분명히 동의한다. 하지만, 위키피디아는 "큰 잘못을 바로잡는" 장소가 아니다; 적어도 이것이 실제로 알고리즘을 구현하는 적절한 방법이라는 것을 확인하는 참고자료가 필요하다. 당신이 당신의 웹사이트에 올린 것을 출처로 사용할 수 없다. 왜냐하면 그것은 스스로 출판되기 때문이다. 또한, 당신도 언급했듯이, 포괄적 상한도 여전히 일반적으로 사용된다. 나는 얼른 고개를 들었다.NET 소스 코드와 그들은 바이너리 검색 구현(소스)에서도 포함 상한선을 사용하는 것 같다. 그래서, 만약 우리가 당신의 버전을 추가한다면, 적어도 현재의 버전도 언급될 필요가 있다고 생각한다, 아마도 "대체 절차" 섹션에서. -조케카 판 히스 (토크) 00:07, 2021년 6월 19일 (UTC)[]
- 나의 빠른 인상은 반쯤 열린 검색 범위를 갖는 것이 나중에 가성 단순화로 도움이 되는 것보다 더 많은 독자들이 기사를 읽기 시작할 때 혼란스럽게 할 가능성이 높다는 것이다. 또한, 다른 비슷한 기사들로부터의 나의 인상은 그러한 변화가 우리가 불평등의 모순을 본다고 생각하는 선의의 신입생들을 계속 되돌리고 그것을 좀더 일관성 있게 보이도록 바꿔야 하는 유지의 악몽으로 이어질 가능성이 높다는 것이다. 그래서 발표 전체를 더 잘 통제할 수 있는 교실과는 상황이 조금 다르다. —David Eppstein (대화) 01:04, 2021년 6월 19일 (UTC)[]
배타적 상한을 사용하는 것은 단지 좋은 프로그래밍 연습일 뿐이다. 나는 내가 "큰 잘못"을 바로잡으려고 하는 것이 아니라고 생각한다 - 우리는 변수에 1을 추가하는 것에 대해 이야기하고 있다. 나는 단지 알고리즘에 좋은 연습을 적용하는 것이다. 그리고, 내가 말했듯이, 좋은 연습은 여기서 지원하는데 중요하다. 많은 숙련된 프로그래머들이 이 프로그램을 잘못 이해하는데, 이는 포괄적 상한을 사용하는 코드에 대해 추론하기 어렵기 때문이다.
실제로 배타적 상한은 매우 훌륭한 프로그래밍 관행으로, C# 버전 8.0은 배타적 상한으로 배열 범위를 지정하는 언어 기능을 추가했다.
조케미는 #5 프로그래밍 언어에 대한 구현을 찾아봤기 때문에, 다른 4개의 언어를 살펴보자.
C의 bsearch 인터페이스는 start + length를 사용한다. LLVM의 구현을 찾을 수 없었다. GCC 구현은 start + length를 사용한다.
C++ STL 함수는 배타적 상한을 사용하는 인터페이스를 가지고 있다. 알고리즘은 std::lower_bound로 구현된다. 참조 코드는 시작 + 길이와 함께 작동한다.
파이썬의 이등분에는 독점적인 상한을 이용한 인터페이스가 있다. 그것은 독점적인 상한선을 사용하여 구현된다.
Java의 Arrays.binarySearch 인터페이스는 독점적인 상한을 사용한다. OpenJDK 구현과 Android 구현은 포괄적 상한을 사용한다. GNU 이행은 배타적 상한을 사용한다.
나는 포괄적 상한선이 사용된다는 것을 부정하지 않는다. 그것은 문헌이 알고리즘에 대해 처음 쓴 방법이다. 대부분의 교과서는 이렇게 제시한다. 우리가 그것을 사용하는 것이 나쁜 프로그래밍 연습이었다는 것을 알기 전에 남겨진 것 같다. 이 언어들 중 어느 것도 인터페이스에 대한 포괄적 한계를 사용하지 않는다는 것을 알아 두십시오. 전혀. "이것이 실제로 알고리즘을 구현하는 적절한 방법이라는 것을 확인하는 참조가 필요하다"고 한다면, 나는 그것이 전부라고 말하고 싶다.
나는 위키피디아 페이지가 시작+길이 또는 배타적 상한을 사용하든 상관하지 않는다. 둘 중 하나는 훌륭한 프로그래밍 연습이다. 데이빗이 선의의 신입생에게 배타적 상한을 가지고 코드를 수정하는 것에 대해 걱정한다면, 우리는 시작+길이에 동의할 수 있을까?
Mdnahas (대화) 19:09, 2021년 7월 5일 (UTC)[]
- 만약 포괄적 상한선이 "대부분의 교과서가 어떻게 그것을 제시하느냐"라면, 그것은 우리가 어떻게 여기에 그것을 제시해야 하는지에 대한 강한 주장이다. 이런 종류의 일에서 위키피디아는 리더가 아니라 추종자가 되어야 한다. —David Eppstein (대화) 19:39, 2021년 7월 5일 (UTC)[]
- 위키피디아는 "팔로워야 한다"는 위키피디아가 연구나 새로운 장학금을 위한 장소가 아니라는 주장이다. 포괄적 상한을 시작+길이로 변경하는 것은 새로운 아이디어가 아니며, 알고리즘 자체에 중요한 것도 아니다. 게다가, "위키피디아는 추종자가 되어야 한다"고 말할 때, 나는 우리의 참조가 교과서에 있는 것이 아니라 실행 중인 코드여야 한다고 생각한다. 내 생각에는 교과서에서 코드가 벗어난다는 것은 중요한 세부사항이다.
데이비드에게 다음과 같은 출처에 동의하는 것 외에, 나는 여기에 쓰여진 많은 것에 동의하지 않는다. 현재 내가 생각하는 것은 '포용적' 방식, 즉 표적이 될 수 있는 곳의 상하위 위치를 똑같이 취급하고 있는 것이다. 개념상의 알고리즘은 상하의 대칭이다. 제안된 「배타적」방법은 상한과 하한을 다르게 취급하는 것을 제안하고, 이것이 더 낫다고 한다. 음, BS. 알고리즘에 추가 개념을 추가하면 이해하기 더 쉬워지지만, 이해하기 더 어려워진다. 비슷한 경험도 없이 학부생들에게 30번 이상 바이너리 검색을 가르쳤기 때문에 경험 논쟁에도 납득이 가지 않는다. 맥케이(대화) 04:04, 2021년 7월 29일 (UTC)[]
