34. Search for a Range

成都創(chuàng)新互聯(lián)2013年開(kāi)創(chuàng)至今，先為饒平等服務(wù)建站，饒平等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為饒平企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

題意：

根據(jù)給定的排序的整數(shù)數(shù)組和給定值，查找給定值的起始位置和終止位置。如果查找不到指定值則返回起始位置和終止位置都為-1。

處理：

1）在給定的數(shù)組中查找給定值，如果給定值存在，則返回第一次出現(xiàn)的位置；否則返回－1.

2）若返回－1，則返回起始和終止都為－1的數(shù)組；否則，分別前向和后向查找起始和終止位置，返回起始終止位置數(shù)組。

查找指定值使用遞歸進(jìn)行查找。

1）如果下標(biāo)中間值和起始下標(biāo)和終止下標(biāo)一致，且當(dāng)前值不是指定值，則返回－1.

2）如果找到指定值則返回下標(biāo)，否則，返回－1

int
findIndex( int *nums, int begin, int end, int target)
{
    int low  = begin;
    int high = end;
    int mid  = ( low + high ) / 2;
    int value = -1; 
    /* 5 7 7 8 8 10*/
    if ( mid == high && low == mid && *(nums + mid) != target )
    {
        return -1;
    }
    if ( *( nums + mid ) < target )
    {
        value = findIndex( nums, mid + 1, high, target );
    }
    else if ( *( nums + mid ) > target )
    {
        value = findIndex( nums, low, mid, target );
    }
    else if ( *( nums + mid ) == target )
    {
        return mid;
    }
    
    return value;
}

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* searchRange(int* nums, int numsSize, int target, int* returnSize)
{
    int *dest = NULL;
    dest = (int *)malloc(sizeof(int) * 3);
    if ( !dest )
    {
        return NULL;
    }
    
    int mid = findIndex( nums, 0, numsSize - 1, target );
    if ( mid == -1 )
    {
        dest[0] = -1;
        dest[1] = -1;
        dest[2] = '\0';
        *returnSize = 2;
        return dest;
    }
    
    int cnt = mid;
    while ( cnt >= 0 && *( nums + cnt ) == target )
    {
        cnt -= 1;
    }
    
    int index = mid;
    while ( index < numsSize && *( nums + index ) == target )
    {
        index += 1;
    }
    
    dest[0] = cnt + 1;                                                    
    dest[1] = index - 1;
    dest[2] = '\0';
    *returnSize = 2;
    return dest;
}

分享文章：[LeetCode]34.SearchforaRange
文章轉(zhuǎn)載：http://chinadenli.net/article40/iegdho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號(hào)、商城網(wǎng)站、建站公司、網(wǎng)站設(shè)計(jì)、網(wǎng)站制作、云服務(wù)器

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)