소개

요 전날 모두가 좋아하는 에너지 음료의 ZONe보다 'mad_hacker'; Ver1.0.0이 발매되었습니다.
무슨 네이밍입니까? 매드 해커 ...
조속히 사 보았는데, 왠지 캔에 프로그램이 디자인되고 있었습니다.



멋지다! ! 이것은 실행하고 싶습니다 ...!

코드 입력

어쨌든, 우선은 사경입니다.
속여서 코드를 넣습니다.

캔이라고 하는 원통에 그려진 것만으로도 읽기 어려운데, 개행도 없는, 다른 디자인에 코드가 방해되고 있는, 문자색도 보이기 어렵습니다만, 어쨌든 괄호 좋기 때문에 열심히 읽습니다.

전부 캔에 30행 정도의 코드가 있습니다만, 4행 중반까지로 하나의 함수가 끝나고 있는 것 같기 때문에, 이번은 거기까지.

왠지 Javascript라는 언어인 것 같습니다.
경험이 없는 언어입니다만, 왠지 개행하면서 씁니다.

mad_hacker.js

 function binarySearch(arr, val, min, max){
     if (max < min) {
         return false;
     }
     const half = Math.floor(min + (max - min) / 2);
     if(arr[half] === val){
         return half;
     }
     return arr[half] > val ? binarySearch(arr, val, min, half - 1) : binarySearch(arr, val, half + 1, max);
 }

binarySearch(이분 탐색)

함수 이름에서 알기 위해 이것은 이분 탐색 알고리즘입니다.
정렬 된 배열과 목록 중에서 특정 값을 찾는 알고리즘입니다.
Wikipedia님의 예를 참고로, 값을 넣어 보겠습니다.

아래와 같은 배열에서 25를 찾는 것을 생각한다.



위치
1
2
3
4
5
6
7
8
9
10


데이터
1
3
5
11
12
13
17
22
25
28



main.js

// 配列作成
search_list = [1,3,5,11,12,13,17,22,25,28]

// 関数実行
ans = binarySearch(search_list, 25, 0, search_list.length);

// 結果確認
console.log(ans); 

첫 번째 인수는 검색할 배열의 search_list를, 두 번째 인수는 검색 대상인 25를 전달합니다.
세 번째, 네 번째 인수의 min와 max는 검색 대상의 숫자가 아니라 배열의 요소 수를 전달하는 것 같습니다.min는 0이고 max는 search_list.length에서 얻은 배열의 요소 수 (= 10)를 전달합니다.

실행 결과

Javascript 는 미경험으로 환경도 없기 때문에, 이번은 파이자. 이오 로 Javascript 를 실행했습니다.

실행 결과

8

여기서 다시 한번 예제를 살펴보자.

아래와 같은 배열에서 25를 찾는 것을 생각한다.



위치
1
2
3
4
5
6
7
8
9
10


데이터
1
3
5
11
12
13
17
22
25
28


이 25 라는 숫자가 배열의 어느 위치에 있는지 탐색하는 것이 이분 탐색이었습니다.
위치로서는 9 번째입니다만, 배열은 0 시작이므로, 8 로 정답이군요!

요약

포도 소다처럼 맛있었습니다.

ZONe 'mad_hacker'; 는 정렬 된 배열에서 임의의 값을 검색하는 이진 검색을 코딩했습니다.
해커 관계가 있습니까?

하지만 어쨌든 자바 스크립트 미경험이었기 때문에 좋은 공부가되었습니다.

나머지 30행도 아무래도 탐색 알고리즘계 같다. 궁금하네요.
AtCoder와 협력 같아요.
계속은 신경이 쓰이면.