二分查找的实现 缺乏、安全感 2022-08-04 12:56 140阅读 0赞 在一个有序的数组中,查找一个数,可以使用二分查找,但是这个算法也是有很多地方需要注意的。正确的写法如下所示。 int binary_search(int* array,int n,int key) { int low = 0; int high = n-1; int mid; if(high < low) return -1; while(high >= low) { mid = low + ((high-low)>>1); if(array[mid] == key) return mid; else if(array[mid] > key) high = mid-1; else low = mid+1; } return -1; } 但是对于上面的二分查找还有另外一种写法,只不过需要注意上述代码中需要注意的地方。 需要注意的地方就是: 如果high = n-1,while(high>=low) high = middle-1; 如果high = n while(high > low) high = middle; 同时也可以使用二分查找解决查找边界的问题,查找一个数在一个有序数组中的上上界和下边界。 在STL库中有一个函数为upper\_bound函数和一个lower\_bound函数,其中第一个函数为找到一个位置,此位置是最后一个可插入此元素的位置,后一个函数是第一个不小于此元素的值。在STL源码库使用的high>low的思想,我们来继承上述的思想来实现这两个函数。 //找下限 int lower_bound(int* array,int low,int high,int key) { int mid; if(high< low) return -1; while(high>=low) { mid = low + ((high-low)>>1); if(array[mid] < key) low = mid+1; else high = mid-1; //cout<<mid<<endl; } return low; } int upper_bound(int* array,int low,int high,int key) { int mid; if(high < low) return -1; while(high >= low) { mid = low +((high-low)>>1); if(array[mid] > key) high = mid-1; else low = mid+1; } return low; } 在STL中也有这两个函数的实现,但是在STL中的算法,所有的迭代器都是遵循左闭右开的原则,所以在哪里的首先都是high>low,然后再循环中使用的都是high = mid这种思想,在这里使用的都是左闭右闭的原则,所以使用的都是high = mid-1这个做法。
还没有评论,来说两句吧...