Damocles 发表于 2007-11-04 14:26:47

一个array中所有的元素先升序排列，后降序排列称之为Unimodal，Unimodal Search就是要找到这个最大的值，O(lgn)的做法就是二分法查询，如果所取的元素大于两边的元素，则是最大值，如果左面大，就在左半边取，右面大，则在右半边取，直到取到为止。应用在convex中找端点的最大x坐标和最大y坐标。找最大的x坐标就是在原本的排列中进行Unimodal Search，找最大的y坐标就是从找到的最大的x坐标那个点开始寻找到第一个点，在这些点中进行Unimodal Search。代码片段如下，写的很挫，不过还是能运行的。

 1 int middle(int *UnimodalList,int middlenum)
 2 {
 3         if((UnimodalList[middlenum]>UnimodalList[middlenum-1])&&
              (UnimodalList[middlenum]>UnimodalList[middlenum+1]))
 4                 return 1;
 5         else  
 6                 return 0;
 7 }
 8 int left(int *UnimodalList,int middlenum)
 9 {
10         if((UnimodalList[middlenum]<UnimodalList[middlenum-1])&&
              (UnimodalList[middlenum]>UnimodalList[middlenum+1]))
11                 return 1;
12         else 
13                 return 0;
14 }
15  
16 int UnimodalSearch(int * UnimodalList,int * indexp, int * maximump,int start, int end)
17 {
18         int size=NR_UnimodalList;
19         int middlenum=(start+end)/2;
20         if(middle(UnimodalList,middlenum))
21         {
22                 *indexp=middlenum;
23                 *maximump=UnimodalList[middlenum];
24                 return 0;
25         }
26         else if(left(UnimodalList,middlenum))
27         {
28                 return UnimodalSearch(UnimodalList,indexp,maximump,start,middlenum);
29         }
30         else 
31         {
32                 return UnimodalSearch(UnimodalList,indexp,maximump,middlenum,end);
33         }
34         return 1;
35 }
36

关键词(Tag): unimodal search

[linuxkernelnewbies] Unimodal Search - 朴泊斋----Damocles的思想笔记 - 歪酷博客 Ycool.c om

Unimodal Search

Damocles 发表于 2007-11-04 14:26:47

Reply via email to