검지 offer - [정렬 배열 에 숫자 가 나타 나 는 횟수] - JavaScript 구현

제목 설명
정렬 배열 에 나타 난 숫자 를 집계 합 니 다.
사고 분석
이 사고방식 과 방법 은 비교적 간단 하고 거칠다.정렬 배열 이기 때문에 같은 숫자 는 틀림없이 함께 배열 되 어 있 을 것 이다.그래서 두 개의 순환 으로 하 나 는 처음부터 끝까지 찾 아 처음 나타 난 위치 와 마지막 으로 나타 난 위 치 를 찾 습 니 다.다시 상쇄 하면 된다.
구체 적 JS 코드 구현 1

function GetNumberOfK(data, k)
{
    // write code here
    var start = -1
    var end = -1
    for(var i = 0;i < data.length; i++)
    {
        if(data[i]==k)
        {
            start = i;
            break
        }
    }
    for(var j = data.length-1; j>-1; j--)
    {
        if(data[j]==k)
        {
            end = j
            break
        }
    }
    if(start != -1 && end != -1)
    {
        return end - start + 1;
    }
    else
    {
        return 0
    }  
}

사고 분석 2
질서 있 는 배열 을 보면 이분법 을 생각해 야 한다.그러나 전통 적 인 이분법 과 달리 여기 서 같은 값 이 여러 번 나타 날 수 있 고 우 리 는 그 가 나타 난 첫 번 째 와 마지막 을 찾 아야 한다.그 러 니까 한 단계 더 판단 해 야 돼.(주석 에 설명 이 있 음)
구체 적 JS 코드 구현 2

	function GetNumberOfK(data, k)
	{
    	// write code here
    	if(data.length == 0)
    	{
    		return 0;
    	}
    	var first = theFirst(data,0,data.length-1,k)
    	var last = theLast(data,first-1,data.length-1,k)
    	if(first!=-1 && last!=-1)
    	{
    		return last-first+1;
    	}
    	else
    	{
    		return 0;
    	}
    	
	}
	//       K   
	function theFirst(data,start,end,k)
    {
        if(start>end)
        {
            return -1;
        }
        var mid = parseInt((start+end)/2)
        if(data[mid]>k)
        {
            end = mid - 1;
            return theFirst(data,start,end,k)
        }
        else if(data[mid]<k)
        {
            start = mid + 1
            return theFirst(data,start,end,k)
        }
        //          mid-1  k  ，             。
        else if((mid-1>=0) && (data[mid-1]==k))
        {
        	return theFirst(data,start,mid-1,k)
        }
        else
        {
            return mid;
        }
    }
    //        K   
    function theLast(data,start,end,k)
    {
        if(start>end)
        {
            return -1;
        }
        var mid = parseInt((start+end)/2)
        if(data[mid]>k)
        {
            end = mid - 1;
            return theLast(data,start,end,k)
        }
        else if(data[mid]<k)
        {
            start = mid + 1
            return theLast(data,start,end,k)
        }
        //          mid+1  k  ，              。
        else if((mid+1<data.length) && (data[mid+1]==k))
        {
        	return theLast(data,mid+1,end,k)
        }
        else
        {
            return mid;
        }
    }