阅微客栈

注册或登录 (丢失密码?):

用户名：
密码：

记住我

阅微客栈 » 头脑风暴

1. 

   zhang
   神

   在一个旋转过的有序数组（比如3 4 5 1 2）上实现二分查找。

   发布于 1 年 之前 #
2. 

   szuxjq
   Member

   example:
   11 12 13 14 15 16 17 18 19 20 4 5 6 7 8 9 10
   suppose ascending from left to right
   a_0 > a_n
   a_m: middle position, m = (0 + n)/2
   a_m > a_0 --> the left partial is ascending
   a_m < a_n --> the right partial is ascending

   b = 5
   a_m = 19
   a_m > a_0 > a_n > b --> b sits in the right partial

   19 20 4 5 6 7 8 9 10

   a_0 > a_n > a_m > b --> b sits in the left partial

   19 20 4 5 6

   a_0 > a_n > b > a_m --> b sits in the right partial

   4 5 6

   a_n == b

   发布于 1 年 之前 #
3. 

   521zheng
   Member

   为何不找到分界点，然后判断在左侧还是右侧查找呢？
   测试通过的算法
   int binarysearch(int key, int* arr, int n)
   {
   int low = 0;
   int high = n-1;

   while(low<=high)
   {
   int mid = (low+high)/2;
   if(arr[mid] == key)
   return mid;
   if(arr[mid]<key) low = mid+1;
   else high = mid-1;
   }
   return -1;
   }
   int getoffset(int *arr, int n)
   {
   if(n<=1) return 0;
   if(arr[0] <arr[n-1])return 0;

   int low =0;
   int high= n-1;

   while(high-low>1)
   {
   int mid = (low+high)/2;
   if(arr[mid] >=arr[low]) low = mid;
   else high = mid;

   }

   return high;

   }
   int searchlooparray(int key, int * arr, int n)
   {
   int offset = getoffset(arr,n);
   if(offset ==0) return binarysearch(key, arr, n);
   if(key>=arr[0] && key <=arr[offset-1])
   return binarysearch(key, arr, offset);
   else if(key>=arr[offset] && key<=arr[n-1])
   {
   int result = binarysearch(key,arr+offset, n-offset);
   return result==-1 ? result:offset + result;
   }
   else return -1;
   }

   发布于 7 月 之前 #

该主题的 RSS Feed

回复

你必须 登录 后发帖。