• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-80  評(píng)論-24  文章-0  trackbacks-0
            今天看編程之美,3.11里面有個(gè)改錯(cuò)題,是針對(duì)一個(gè)二分查找算法的糾錯(cuò),先說(shuō)下題目:找出一個(gè)有序(字典序)字符串?dāng)?shù)組arr中值等于字符串v的元素的序號(hào),如果有多個(gè)元素滿足條件,則返回其中序號(hào)最大的。
            要說(shuō)算法這個(gè)問(wèn)題確實(shí)不難,但是寫程序的話需要注意一些地方,書中已經(jīng)寫的比較完美了,就不貼了,這里貼一個(gè)通用版本,也是模仿斯坦福公開課《編程范式》中講解的來(lái)寫的,這個(gè)bisearch()和c庫(kù)中的bsearch()很像。

             1 int bisearch(const void *arr, 
             2     const void *elem, 
             3     int elem_size, 
             4     int elem_num, 
             5     int (*fcmp)(const void *, const void *)) {
             6   int low = 0;
             7   int high = elem_num - 1;
             8   int mid;
             9 
            10   while (low < high - 1) {
            11     mid = ((high - low) >> 1) + low;
            12     int status = 
            13       fcmp((const void *)((char *)arr + mid * elem_size), 
            14           (const void *)elem);
            15     if (status <= 0) {
            16       low = mid;
            17     } else {
            18       high = mid;
            19     }
            20   }
            21 
            22   if (fcmp((const void *)((char *)arr + high * elem_size), 
            23         (const void *)elem) == 0) {
            24     return high;
            25   } else if (fcmp((const void *)((char *)arr + low * elem_size), 
            26         (const void *)elem) == 0) {
            27     return low;
            28   } else {
            29     return -1;
            30   }
            31 }
            32 

            可以看到如果題目變一下,那么上面的函數(shù)也需要改變,比如,如果有多個(gè)元素滿足這個(gè)條件,則返回最小的序號(hào),那么程序修改如下:

            int bisearch(const void *arr, 
                const void *elem, 
                int elem_size, 
                int elem_num, 
                int (*fcmp)(const void *, const void *)) {
              int low = 0;
              int high = elem_num - 1;
              int mid;

              while (low < high - 1) {
                mid = ((high - low) >> 1) + low;
                int status = 
                  fcmp((const void *)((char *)arr + mid * elem_size), 
                      (const void *)elem);
                if (status >= 0) {
                  high = mid;
                } else {
                  low = mid;
                }
              }

              if (fcmp((const void *)((char *)arr + low * elem_size), 
                    (const void *)elem) == 0) {
                return low;
              } else if (fcmp((const void *)((char *)arr + high * elem_size), 
                    (const void *)elem) == 0) {
                return high;
              } else {
                return -1;
              }
            }

            其實(shí)也就是修改一下比較的順序。
            如果要求大于v的最小的數(shù)組元素的序號(hào)i呢?我們依然先求等于v的最大的序號(hào)j,不過(guò)在確定low和high之后,需要如下考慮:
            若arr[low] > v,那么我們可以肯定low即為i
            若arr[high] < v,那么我們也可以肯定沒有比v大的元素,返回-1
            若arr[high] == v,那么如果high = elem_num - 1,則說(shuō)明數(shù)組中所有元素都小于等于v,則返回-1,否則返回high + 1
            否則返回high
            程序如下:

             1 int bisearch(const void *arr, 
             2     const void *elem, 
             3     int elem_size, 
             4     int elem_num, 
             5     int (*fcmp)(const void *, const void *)) {
             6   int low = 0;
             7   int high = elem_num - 1;
             8   int mid;
             9 
            10   while (low < high - 1) {
            11     mid = ((high - low) >> 1) + low;
            12     int status = 
            13       fcmp((const void *)((char *)arr + mid * elem_size), 
            14           (const void *)elem);
            15     if (status <= 0) {
            16       low = mid;
            17     } else {
            18       high = mid;
            19     }   
            20   }
            21 
            22   int stlow = 
            23     fcmp((const void *)((char *)arr + low * elem_size), 
            24         (const void *)elem);
            25   int sthigh = 
            26     fcmp((const void *)((char *)arr + high * elem_size), 
            27         (const void *)elem);
            28   if (stlow > 0) {
            29     return low;
            30   } else if (sthigh < 0) {
            31     return -1; 
            32   } else if (sthigh == 0) {                                                                                                  
            33     if (high == elem_num - 1) {
            34       return -1; 
            35     } else {
            36       return high + 1;
            37     }   
            38   }
            39   return high;
            40 }

            如果要求小于v的最大的數(shù)組元素的序號(hào)i呢?我們依然先求等于v的最小的序號(hào)j,不過(guò)在確定low和high之后,需要如下考慮:
            若arr[low] > v,那么我們可以肯定沒有比v大的元素,返回-1 
            若arr[high] < v,那么返回high
            若arr[low] == v,那么如果low = 0,則說(shuō)明數(shù)組中所有元素都大于等于v,則返回-1,否則返回low - 1
            否則返回low
            程序如下: 

             1 int bisearch(const void *arr, 
             2     const void *elem, 
             3     int elem_size, 
             4     int elem_num, 
             5     int (*fcmp)(const void *, const void *)) {
             6   int low = 0;
             7   int high = elem_num - 1;
             8   int mid;
             9 
            10   while (low < high - 1) {
            11     mid = ((high - low) >> 1) + low;
            12     int status = 
            13       fcmp((const void *)((char *)arr + mid * elem_size), 
            14           (const void *)elem);
            15     if (status >= 0) {
            16       high = mid;
            17     } else {
            18       low = mid;
            19     }   
            20   }
            21 
            22   int stlow = 
            23     fcmp((const void *)((char *)arr + low * elem_size), 
            24         (const void *)elem);
            25   int sthigh = 
            26     fcmp((const void *)((char *)arr + high * elem_size), 
            27         (const void *)elem);
            28   if (stlow > 0) {
            29     return -1; 
            30   } else if (sthigh < 0) {
            31     return high;
            32   } else if (stlow == 0) {
            33     if (low == 0) {
            34       return -1; 
            35     } else {
            36       return low - 1;
            37     }   
            38   }
            39   return low;
            40 }
            posted on 2012-09-02 18:37 myjfm 閱讀(512) 評(píng)論(1)  編輯 收藏 引用 所屬分類: 算法基礎(chǔ)

            評(píng)論:
            # re: 二分查找剖析 2013-04-07 13:05 | jq
            最后一例:要求小于v的最大的數(shù)組元素的序號(hào)i
            最后的判斷似乎不夠簡(jiǎn)潔,想探討一下,盼賜教,多謝

            28 if (stlow > 0) {
            29 return -1;
            30 } else if (sthigh < 0) {
            31 return high;
            32 } else if (stlow == 0) {
            33 if (low == 0) {
            34 return -1;
            35 } else {
            36 return low - 1;
            37 }
            38 }
            39 return low;

            感覺可以優(yōu)化為下列:
            if(sthigh<0) {
            return high;
            } else if(stlow<0) {
            return low;
            }
            else {
            return -1;
            }
            因?yàn)?6行永遠(yuǎn)不會(huì)執(zhí)行到:
            若stlow==0, 則low == 0
            反正法: 若 low>0且stlow==0, 因?yàn)閯傞_始low=0, 所以必定在while循環(huán)中被改變:
            而low被修改的前提條件: arr[mid]< elem , 所以被改后 low=mid, arr[low]<element==>stlow!=0
              回復(fù)  更多評(píng)論
              
            一本久久a久久精品vr综合| 欧美精品久久久久久久自慰| 色噜噜狠狠先锋影音久久| 久久精品夜色噜噜亚洲A∨| 思思久久99热只有频精品66| 久久亚洲高清观看| 三级片免费观看久久| 97精品国产97久久久久久免费| 亚洲国产成人久久一区WWW| 国产日韩久久免费影院| 欧美久久综合性欧美| 亚洲国产高清精品线久久| 久久99国产精品久久久| 久久发布国产伦子伦精品| 久久一日本道色综合久久| 理论片午午伦夜理片久久| 欧美亚洲另类久久综合婷婷| 精品久久久久久久久午夜福利| 久久久久亚洲av无码专区| 美女久久久久久| 久久99精品九九九久久婷婷| 无码精品久久一区二区三区| 久久最近最新中文字幕大全 | 色成年激情久久综合| 亚洲欧美伊人久久综合一区二区| 色妞色综合久久夜夜| 久久人人爽人人爽人人片AV麻烦 | 亚洲精品乱码久久久久久中文字幕| 久久婷婷国产麻豆91天堂| 久久亚洲美女精品国产精品| 久久国产精品无| 久久久久亚洲爆乳少妇无| 狠狠精品久久久无码中文字幕 | 亚洲精品无码专区久久同性男| 99热都是精品久久久久久| 国产精品无码久久久久久| 久久久久久亚洲AV无码专区| 人妻精品久久无码区| 久久综合噜噜激激的五月天| 99精品国产99久久久久久97 | 久久99热只有频精品8|