首页 > 代码库 > 一天一道算法题---6.26---二分查找

一天一道算法题---6.26---二分查找

感谢微信平台---一天一道算法题----每天多一点进步--

好累啊  现在在用win7自带的输入法 打起来真麻烦 快点把这2天的搞完就重装了

还是直接来源于----〉 待字闺中

 

分析

给定一个数组A,其中有一个位置被称为Magic Index,含义是:如果i是Magic Index,则A[i] = i。假设A中的元素递增有序、且不重复,请给出方法,找到这个Magic Index。更进一步,当A中允许有重复的元素,该怎么办呢?

没有重复元素的情况

一些同学在遇到这个题目的时候,往往会觉得比较简单。扫描一遍,不就ok了么?O(n)的。很简单呀。可是,大家要注意到,还有一 个条件没有用:A中的元素是有序递增的。这个条件,并不是放在这里迷惑大家的,而是有更大的作用的。这个时候,该如何想呢?O(n)不是最好的方法,更好 的是什么呢?怎么利用数组有序呢?在有序的数组中查找一个满足特定元素的条件,我们通常会想到二分查找。 我们来回顾一下二分查找,对于要查找的目标t,我们首先与数组中间的元素比较,如果t大于中间的元素,则在右半部分继续查找;如果t小于中间的元素,则在 左半部分,继续查找。

那么,我们的题目能够利用上述的思想呢?我们来看一个具体的例子:

0223456
-10-51241012

mid=3,A[mid] = 2,即A[mid] < mid。接下来,我们应该在哪一边查找呢?我们知道数组的元素是递增有序,且不重复的,也就是说,在A[mid]左边的元素,比A[mid]都要小,没有 重复,意味着什么呢?每向左移动一位,至少减1。所以,在mid左边,不可能有一个i,A[i]=i的。如果有,根据前面的分析,我们知道A[mid] - A[i] >= mid - i, 如果A[i] = i,则,A[mid] >= mid, 这与事实A[mid] < mid相悖。所以,接下来,只能在右边进行查找。代码与二分查找也很像。

有重复元素的情况

如果数组A中,有重复元素,是什么情况呢?经过前面的分析,我们知道,是否有重复的主要差别在,数组的元素从右到左进行递减,每次不一定至少是1了,有可能是0了。让我们直观的看一下影响吧。

0223456
-1022291012

看上面的数组,同样A[mid] < mid。我们应该继续查右边么?显然,右边并不存在Magic Index。查找右边,就会找不到这样的Magic Index。此时,应该如何处理呢?我们无法确定,Magic Index是在左边,还是在右边了。那就两边都递归进行处理吧。

在这里还有一个小技巧,我们就是要分别递归处理[0, mid - 1]和[mid + 1, end](end是数组长度-1)么?我们看一个具体的例子:

022345678
-10222210121320

这个例子,当我们进行左半部分递归处理的时候,需要考虑的范围是[0, 3]。可实际上,我们只需要考虑[0, 2]。原因是,数组元素在mid=4的左边的值都要小于或者等于A[mid]=2,所以最大的一个有可能是Magic Index的,就是index为A[mid]的情况。所以,这时右边的边界应该是min(mid - 1, A[mid])。

那么,右边的情况呢?如下例子:

022345678
-10222210121320

此时,要在右半部分进行查找,范围一般是[5, 8]。但是,由于数组有序,后面的值,一定是大于等于A[mid]=9的。所以,有可能是Magic Index的最小Index是9,也就是说右边的递归,应该是从索引为9的位置开始。此例,就意味着,无需处理右边了。

 

code:来源于--->阳光可乐

 

 1 #include<iostream> 2 using namespace std; 3  4  5 int magicIndex1(int A[],int low,int high){//无重复元素情况 6     int mid = low+(high-low)/2; 7     if(A[mid] == mid){ 8         return mid; 9     }10     else if(A[mid] > mid){//如果A[mid]>mid,则用所有所有mid的元素都不可能存在A[i]==i11         //因为元素递增有序且无重复元素12         return magicIndex1(A,low,mid-1);13     }14     else{15         //原理同上16         return magicIndex1(A,mid+1,high);17     }18 }19 20 int magicIndex2(int A[],int low, int high){//有重复元素情况21     if(high < low )22         return -1;23     int mid = low+(high-low)/2;24     if(A[mid] == mid){25         return mid;26     }27     else{28         int left = magicIndex2(A,low,mid-1);29         int right = magicIndex2(A,mid+1,high);30         if(left != -1)31             return left;32         else 33             return right;34     }35 }36 37 38 int main(){39     int A[5]={-1,1,1,2,3};//{-1,0,1,2,4};40     //cout<<magicIndex1(A,0,4)<<endl;41     cout<<magicIndex2(A,0,4)<<endl;42     return 0;43 }
View Code