이 글은 주로 JS 바이너리 검색 알고리즘과 코드를 공유합니다. 필요한 친구들이 참고하면 도움이 될 것입니다.
4.1 이진 검색
알고리즘 소개
반 검색이라고도 불리는 이진 검색은 정렬된 배열에서 특정 요소를 찾는 검색 알고리즘입니다. 검색 과정은 다음과 같은 단계로 나눌 수 있습니다.
(1) 먼저 정렬된 배열의 중간 요소부터 검색을 시작합니다. 해당 요소가 대상 요소(즉, 찾을 요소)인 경우 검색이 수행됩니다. 프로세스가 종료됩니다. 그렇지 않으면 다음 단계로 진행합니다.
(2) 대상 요소가 중간 요소보다 크거나 작은 경우, 중간 요소보다 크거나 작은 배열의 절반 영역을 검색한 후 첫 번째 단계를 반복합니다.
(3) 특정 단계의 배열이 비어 있으면 대상 요소를 찾을 수 없다는 의미입니다.
참조 코드:
비재귀 알고리즘
function binary_search(arr,key){ var low=0, high=arr.length-1; while(low<=high){ var mid=parseInt((high+low)/2); if(key==arr[mid]){ return mid; }else if(key>arr[mid]){ low=mid+1; }else if(key<arr[mid]){ high=mid-1; }else{ return -1; } } }; var arr=[1,2,3,4,5,6,7,8,9,10,11,23,44,86]; var result=binary_search(arr,10); alert(result); // 9 返回目标元素的索引值
재귀 알고리즘
function binary_search(arr,low,high,key){ if(low>high){ return -1; } var mid=parseInt((high+low)/2); if(arr[mid]==key){ return mid; }else if(arr[mid]>key){ high=mid-1; return binary_search(arr,low,high,key); }else if(arr[mid]<key){ low=mid+1; return binary_search(arr,low,high,key); } }; var arr=[1,2,3,4,5,6,7,8,9,10,11,23,44,86]; var result=binary_search(arr,0,13,10); alert(result); // 9 返回目标元素的索引值
위 내용은 JS 바이너리 검색 알고리즘 및 코드 공유의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!