JavaScript 절반 찾기(이분 찾기)알고리즘 원리 와 실현 방법 예시

본 고의 실례 는 자 바스 크 립 트 반절 탐색(이분 탐색)알고리즘 의 원리 와 실현 방법 을 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
1.문제 설명:
오름차 배열 에서 검색 할 값 의 색인 위 치 를 절반 으로 찾 습 니 다.예:

var a=[1,2,3,4,5,6,7,8,9];
search(a,3);//  2
search(a,1);//   ，  0
search(a,9);//   ，  8
search(a,0);//       ，  "         "
search(a,10);//       ，  "         "

주:반절 탐색 은 질서 있 는 배열 에서 만 유효 하 며 무질서 한 배열 은 검색 기능 을 실현 할 수 없습니다.예 를 들 어[10,5,6,7,8,9,20]에서 10 을 찾 으 면 중간 색인 위치의 값 은 7 이 고 7 대 10 보다 작 기 때문에 오른쪽 배열 에서 찾 아야 한다.실제로 10 을 찾 을 수 없다.
2.나의 실현

function search(arr,num) {
  var l=arr.length;
  var left=0;
  var right=l-1;
  var center=Math.floor((left+right)/2);
  while(left<=l-1&&right>=0){
    if (arr[center]==num) return center;
    if (left==right) return "        ";
    if (arr[center]>num) {
      right=center-1;
      center=Math.floor((left+right)/2);
    }else if (arr[center]<num) {
      left=center+1;
      center=Math.floor((left+right)/2);
    }
  }
}
var a=[1,2,3,4,5,6,7,8,9];
console.log(search(a,-2));

설명:
1.기본 적 인 사고방식:
매번 비교 할 때마다 배열 중간 색인 위치의 값 이 찾 으 려 는 값 보다 크 면 배열 중간 위치 이전의 하위 배열 에서 찾 습 니 다.반면 배열 의 중간 색인 위치 값 이 찾 으 려 는 값 보다 크 면 배열 의 중간 위치 에 있 는 하위 배열 에서 찾 습 니 다.배열 의 중간 색인 위치 값 이 찾 을 값 과 같다 면 이 색인 위 치 를 되 돌려 줍 니 다.
2.left 는 검색 범위 의 시작 위 치 를 정의 하고 right 는 검색 범위 의 끝 위 치 를 정의 하 며 center 는 검색 범위 의 중간 위 치 를 정의 합 니 다.
3.while 의 논리 적 설명:
(1)구체 적 으로 몇 번 을 찾 는 지 모 르 기 때문에 while 는 비교적 좋 은 선택 이다.
(2)순환 종료 조건:
a.right 가 0 보다 작 으 면 더 이상 찾 지 않 고 아무리 매 달 려 도 결과 가 나 오지 않 습 니 다.예 를 들 어a=[1,2,3,4,5,6,7,8,9]에서 0 을 찾 으 면 검색 범위 가left=0로 바 뀌 고right=0,center=0일 때 while 문 구 를 찾 으 면arr[center]>0로 인해 실 행 됩 니 다.

right=center-1;
center=Math.floor((left+right)/2);

획득right=-1이때 순환 에 들 어가 지 않 아야 합 니 다.
b.일단left>l-1이 되면 더 이상 찾 지 않 고 더 이상 매달 려 도 결과 가 없 을 것 입 니 다.예 를 들 어a=[1,2,3,4,5,6,7,8,9]에서 10 을 찾 으 면 검색 범위 가left=8로 바 뀌 고right=8,center=8일 때 while 문 구 를 찾 으 면arr[center]<10이 므 로 실 행 됩 니 다.

left=center;
center=Math.floor((left+right)/2);

획득left=9,이 때 는 순환 에 들 어가 지 않 아야 합 니 다.
4.항상 center 를 통 해 찾 을 값 에 일치 합 니 다.
5.Math.floor검색 범위 의 길이 가 짝수 인 상황 을 처리 했다.
6.당left==right이 되 었 지만arr[center]==num을 집행 하지 않 으 면 결론 을 얻 을 수 없다.
7.arr[center]==num일 때 전체 함수 가 끝 났 고 뒤의 문 구 는 실행 되 지 않 습 니 다.
상기 코드 는 온라인 HTML/CSS/JavaScript 코드 실행 도구http://tools.jb51.net/code/HtmlJsRun를 사용 하여 다음 과 같은 테스트 실행 결 과 를 얻 었 습 니 다.

자 바스 크 립 트 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있다.
본 고 에서 말 한 것 이 여러분 의 자 바스 크 립 트 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.