以區間為機關的二分查找

【2019回家過年前的一記】

問題場景：

區間的格式如下，整體為一個Json字元串，每個區間的startTime和endTime都是按照從小到大的順序排列的。

"[{\"endTime\":1578633955,\"startTime\":1578626876},{\"endTime\":1578640268,\"startTime\":1578634050},{\"endTime\":1578642086,\"startTime\":1578640291},{\"endTime\":1578643084,\"startTime\":1578642639}]"

現在給定一個使用者需要查找的時間段：

"startTime":1578585600,

"endTime":1578644000

要求：傳回該時間段内的所有區間，若查找的時間點位于某個區間中間，需要對該區間進行分割隻傳回所需要的那一段。

代碼思路：

●首先将每個小區間的startTime和endTime依次存入一個數組中；

●使用二分查找該數組快速确定使用者請求的時間段與原始區間的交集起始點位置index；

●從該位置開始将符合要求的區間依次放入新的json串中，期間需要對首尾兩個區間進行特殊處理

【0,1】【2,3】【4,5】【6,7】  

begin=0,end=7,mid=3

因為小區間都是兩個元素，故mid在最後一步（begin+1 == end）之前都是奇數，即某個小區間的endTime。

然後最後一步有兩種情況：

●使用者請求的時間段的startTime落在【2,3】中；（begin==2；end==3；mid=（2+3）>>1即mid == begin）

●使用者請求的時間段的startTime落在1】，【2中，即落在一個無效的點上。（begin==1；end==2；mid=（1+2）>>1即mid == begin）

可見兩種情況下都有mid == begin，是以可将其作為一個結束條件。

不論mid為奇數還是偶數，當mid指向的startTime或者endTime和使用者請求的startTime相等時，說明找到交集的起點位置了，二分查找結束，這是另一個結束條件，那麼index記錄下該位置是原始區間的第幾個，然後在進行後續處理。index=（mid+1）/2（當mid為偶數時index本為mid/2，但為了統一起見，将其寫成(mid+1)/2了，并不影響最後的結果）

以下兩種極端情況的處理都放在二分查找完畢後，這樣可以保證二分查找過程的清晰度：

●使用者請求的區間在所有原始區間的前面且無交集，這樣最後的結果應該為空；

●使用者請求的區間在所有原始區間的後面且無交集，這樣最後的結果應該為空；

函數代碼如下：

/**Writen By: zzg**/
/**Date: 2020/01/20**/

static void filterConcretInterval(long int startTime, long int endTime, JsonParser & sliceList)
    {
        unsigned int begin = 0;
        unsigned int end = 0;
        unsigned int mid = 0; 
        unsigned int index = 0;
        unsigned int listSize = 0;
        JsonParser newList;

        if(sliceList.size() == 0){
            return ;
        }
        if(startTime == endTime){
            sliceList.clear();
            return ;
        }
        listSize = sliceList.size();

        //将所有區間轉化為一維數組
        long int timeArray[listSize << 1];

        for(unsigned int i = 0, j = 0; i < listSize, j < ((listSize << 1) - 1); i++, j++){
            if(sliceList[i]["startTime"].isInt64() && sliceList[i]["endTime"].isInt64()){
                timeArray[j] = sliceList[i]["startTime"].asInt64();
                j++;
                timeArray[j] = sliceList[i]["endTime"].asInt64();
            }
        }
        end = (listSize << 1) - 1;
        while(begin <= end){    //取等号意義在于當begin==end，即隻有一個區間時，index的取值
            mid = (begin + end) >> 1;
            if((timeArray[mid] == startTime) || (mid == begin)){
                index = (mid+1) >> 1;
                break;
            }else if(timeArray[mid] > startTime){
                end = mid;
            }else{
                begin = mid;
            }
        }

        if(sliceList[index]["endTime"] <= startTime){
            index++;
        }
        if(index == listSize){
            sliceList.clear();
            return ;
        }
        if(sliceList[index]["startTime"] < startTime){
            sliceList[index]["startTime"] = startTime;
        }

        for(unsigned int i = index; i < sliceList.size(); i++){
            if(sliceList[i]["endTime"].isInt64() && sliceList[i]["startTime"].isInt64()){
                if(sliceList[i]["startTime"] >= endTime) break;
                newList[i-index] = sliceList[i];
                if(sliceList[i]["endTime"] >= endTime){
                    newList[i-index]["endTime"] = endTime;
                    break;
                }
            }
        }
        sliceList.clear();
        sliceList = newList;
    }
           

另解：

當然，如果不考慮時間複雜度，可以構造一個包含startTime和endTime的結構體，直接将每個小區間當做一個結構體對象插入一個set容器（以紅黑樹為底層實作）中，此時構造了一顆紅黑樹。然後将使用者請求的startTime和endTime分别作為兩個結構體對象插入到該set中，如果插入失敗，則說明set中已經存在該時間點，傳回該節點的iterator。最後隻需周遊兩次插入位置之間的節點即可得到使用者請求的區間了。(^_^)