알고리즘 심득 - 2 분 찾기

2 분 찾기 템 플 릿
2 분 검색 은 질서 있 는 배열 에서 특정한 요 소 를 찾 거나 특정한 요 소 를 삽입 하 는 데 자주 사용 된다. 2 분 검색 방법 에 대한 상세 한 소개 와 분석 은 이 큰 신 급 문 제 를 볼 수 있다. '배제 법' (감 치 사상) 으로 2 분 검색 문 제 를 쓰 고 다른 2 분 검색 모델 과 비교 할 수 있다.
검색 구간 에 대한 선택 이 다 를 때마다 여러 가지 템 플 릿 이 있 습 니 다. 여 기 는 제 가 가장 자주 사용 하 는 사고방식 템 플 릿 만 씁 니 다.

left = 0
right = arr.lenght-1
while(left < right) {
	//          
	mid = Math.floor((left + right)/2)
	if(target > arr[mid]) {
		left = mid+1
	} else {
		right = mid
	}
}
//    return left         left      
// 1.     target  ，  left  target     
// 2.      target  ，  left    target     ，        
return left

left 로 돌아 가 는 의 미 를 이해 하려 면 버클 의 이 문 제 를 푸 는 것 을 권장 합 니 다. 삽입 위 치 를 검색 하 는 것 을 권장 합 니 다.
배열 에 target 요소 가 있 는 지 판단 합 니 다.target 이 있 는 지 판단 하려 면 먼저 if..else 에 하나의 target == arr[mid] 판단 을 추가 하고 찾 으 면 바로 return mid 해 야 한다. 그러나 여기 서 특수 한 상황 을 주의해 야 한다. 예 를 들 어 배열 [5,7,8,10] 에서 찾 으 면 10 바로 뛰 어 나 left=mid+1 순환 을 해 야 한다. 더 이상 left right 과 같 는 지 판단 할 수 없다.이 bug 를 해결 하기 위해 서 순환 이 끝 난 후에 판단 을 추가 합 니 다.

//          ，      
left = 0
right = arr.lenght-1
while(left < right) {
	//          
	mid = Math.floor((left + right)/2)
	if(target > arr[mid]) {
		left = mid+1
	} else if(target == arr[mid]) {
		return mid
	} else {
		right = mid
	}
}
//        ，   ，   left  
if(arr[left] == target) return left
//        -1
return -1

사실은 더 간단 한 해결 방법 이 있 습 니 다. 판단 조건 을 추가 하지 않 아 도 됩 니 다. 바로 처음에 값 을 부여 할 때 while 를 직접 양보 하고 right 에 길 이 를 하나 더 주면 기 존의 문 제 를 피 할 수 있 고 영원히 얻 지 못 할 것 입 니 다 target. 없 을 것 입 니 다 right = arr.lenght.
정렬 배열 에 나타 난 숫자 를 통계 합 니 다.

var search = function(nums, target) {
    let left = 0;
    //               
    let right = nums.length;
    let count = 0;
    while(left < right) {
        mid = Math.floor((right + left)/2);
        if(nums[mid] > target) {
            right = mid;
        } else if(nums[mid] < target){
            left = mid+1;
        } else {
            //       ，     
            let a = mid;
            let b = mid-1;
            //     
            while(nums[mid] == nums[a]) {
                a++;
                count++;
            }
            //     
            while(nums[mid] == nums[b]) {
                b--;
                count++;
            }
            return count;
        }
        
    }
    return count;
};

부분 정렬 배열 에서 의 응용
일부 배열 은 일부 질서 만 있 을 뿐 2 분 으로 요소 의 위 치 를 찾 을 수 있다. 예 를 들 어 회전 정렬 배열 을 검색 하 는 것 이다.