Amazon Intern面经

xiaozhuxiaozhu 发表于 2016-1-9 07:43
我读书特别少，你千万别骗我。。。
0 + ( 6-0)/2 = 3
arr[3] = 10...

不明白你在讲什么。。。。pivot是指极点。。。

yhfyhf 发表于 2016-1-9 07:45
不明白你在讲什么。。。。pivot是指极点。。。

你这里说的pivot难道部是binary search里面的mid index么？？？

xiaozhuxiaozhu 发表于 2016-1-9 07:47
你这里说的pivot难道部是binary search里面的mid index么？？？

不是啊。。。。是极点。。。。

yhfyhf 发表于 2016-1-9 07:49
不是啊。。。。是极点。。。。

请教，啥是binary search pivot?????


https://www.google.com/search?q= ... iw=1280&bih=672

xiaozhuxiaozhu 发表于 2016-1-9 07:50
请教，啥是binary search pivot?????

我没说这叫binary search pivot... 我只是把极点叫作pivot。。。说实话我不知道极点用英文怎么说。。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

xiaozhuxiaozhu 发表于 2016-1-9 07:56
binary search一般的是先找mid point吧？（可以说成pivot啊，都能理解啥意思）。。
我不太清楚，你说的p ...

我已经在帖子里讲了，我觉得8楼也讲得很清楚了。。额。。如果你还不明白我的意思，我觉得我也解释不清楚了。。。

先找到pivot点也就是题目中的那个最小点，然后将数组分成两部分之后继续做BS

1. public int search(int[] nums, int target) {
   
2.         // find the smallest point
   
3.         int start = 0, end = nums.length - 1;
   
4.         int pivot = 0;
   
5.         while(start <= end) {
   
6.             int mid = start + (end - start) / 2;
   
7.             if(nums[mid] == target) {
   
8.                 return mid;
   
9.             }
   
10.             if(mid > 0 && mid < nums.length - 1) {
    
11.                 if(nums[mid - 1] > nums[mid] && nums[mid + 1] > nums[mid]) {
    
12.                     pivot = mid;
    
13.                     break;
    
14.                 }
    
15.                 else if(nums[mid - 1] < nums[mid]) {
    
16.                     end = mid - 1;
    
17.                 }
    
18.                 else {
    
19.                     start = mid + 1;
    
20.                 }
    
21.             }
    
22.             else {
    
23.                 break;
    
24.             }
    
25.         }
    
26.         
    
27.         start = 0;
    
28.         end = pivot;
    
29.         while(start <= end) {
    
30.             int mid = start + (end - start) / 2;
    
31.             if(nums[mid] == target) {
    
32.                 return mid;
    
33.             }
    
34.             else if(nums[mid] > target) {
    
35.                 start = mid + 1;
    
36.             }
    
37.             else {
    
38.                 end = mid - 1;
    
39.             }
    
40.         }
    
41.         
    
42.         start = pivot;
    
43.         end = nums.length - 1;
    
44.         while(start <= end) {
    
45.             int mid = start + (end - start) / 2;
    
46.             if(nums[mid] == target) {
    
47.                 return mid;
    
48.             }
    
49.             else if(nums[mid] < target) {
    
50.                 start = mid + 1;
    
51.             }
    
52.             else {
    
53.                 end = mid - 1;
    
54.             }
    
55.         }
    
56.         
    
57.         
    
58.         return -1;
    
59.     }

复制代码