이진 검색
4084 단어 algorithmssearchjavascriptbinary
target 요소의 정렬된 배열arr[]에서 대상 값n을 찾는 이진 검색 알고리즘을 설명합니다.요약
정보가 정렬되어 있다는 것을 알고 있으므로 시간 복잡도가 O(n)인 선형 검색을 사용하지 않아도 됩니다.
이진 검색은 O(log n)의 더 나은 시간 복잡도를 가집니다.
예제 문제
정렬된 배열
arr = [1,10,25,220,271,300,355,444,450,500]이 주어지면 배열에서 10의 인덱스를 반환합니다. 10가 배열에 없으면 -1를 반환합니다.참고: 이 배열은 매우 작으며
10가 배열의 인덱스1에 있음을 분명히 알 수 있으므로 for 루프를 사용하여 선형 검색을 수행하는 것이 직관적으로 보일 수 있습니다. 그러나 10,000개 또는 100,000개의 값이 있는 정렬된 배열의 끝 근처에서 일부 숫자의 인덱스를 검색하는 것을 고려하십시오. 이러한 더 큰 배열에서는 시간 복잡성이 중요하며 O(log n) 알고리즘은 선형 검색보다 훨씬 빠르게 인덱스를 반환합니다.단계
인덱스
start 를 가리키도록 0 를 설정하고 인덱스 end 를 가리키도록 array.length-1 를 설정하여 전체 배열의 간격으로 시작합니다.arr: [1,10,25,220,271,300,355,444,450,500]
let start = 0;
let end = arr.length-1; // index 9 is the last element of the array
// we subtract 1 from the array length because
// we start counting from 0
먼저
mid와 start를 더하고 end로 나누어 배열의 2 인덱스를 찾습니다. 합이 홀수이면 나눗셈 결과가 정수가 아니므로 나눗셈 결과floor()가 필요합니다.let mid = Math.floor( (start + end) / 2 ); // mid = floor( (0+9) / 2 ) = floor(4.5) = 4
target mid
/ /
arr: [1,10,25,220,271,300,355,444,450,500]
^ ^
start end
target value: 10
start: 0
mid: 4
value at mid: 25
end: 9
10 )이 mid 의 값과 같은지 확인합니다. 같으면 대상 값의 인덱스로 mid를 반환합니다. 알고리즘의 이 단계에서 mid의 값은 25이며 목표 값10과 같지 않습니다. 목표 값을 찾지 못했기 때문에 목표 값이
mid 의 값보다 작거나 큰지 확인하고 start 또는 end 를 조정하여 검색 간격을 재정의합니다. 목표 값이 mid 의 값보다 작으면 end 인덱스를 mid-1 로 설정하여 배열의 전체 후반부를 버립니다. 목표 값이 mid 의 값보다 크면 start 인덱스를 mid+1 로 설정하여 배열의 첫 번째 절반을 버립니다.if( target < arr[mid] ) {
end = mid-1;
} else if( target > arr[mid] ) {}
start = mid+1;
}
target mid
/ /
arr: [1,10,25,220,271,300,355,444,450,500]
^ ^
start end
target value: 10
start: 0
mid: 4
value at mid: 25
end: 3
이제
end 를 3 로 조정하여 검색 간격을 효과적으로 반으로 줄였으므로 새로운 mid 를 찾아야 합니다.mid = Math.floor( (start + end) / 2 ); // mid = floor( (0+3) / 2 ) = floor(1.5) = 1
target
/
arr: [1,10,25,220,271,300,355,444,450,500]
^ \ ^
start mid end
target value: 10
start: 0
mid: 4
value at mid: 10
end: 3
10 )이 mid 의 값과 같은지 다시 확인합니다. mid의 값은 10이고 대상 값은 10이므로 배열에서 1의 위치로 mid(target)를 반환합니다. 암호
var search = function(nums, target) {
let start = 0;
let end = nums.length-1;
let mid;
while(start <= end) {
mid = Math.floor((start+end)/2);
if(target == nums[mid]) {
return mid;
} else if (target > nums[mid]) {
start = mid+1;
} else {
end = mid-1;
}
}
return -1; // if the target value is not found in the array
// return -1
};
자원
https://leetcode.com/problems/binary-search/
Reference
이 문제에 관하여(이진 검색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/tomkanabay/binary-search-233c텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
