二分查找(算法篇)

2024-06-24 02:36

文章标签 二分查找算法

本文主要是介绍二分查找(算法篇)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法之二分查找

二分查找

概念：

针对于已经预先排序好的数据，每次将数据进行对半查找，然后看它中间的数据是否是要找的，如果是就返回中间位置，不是就判断该数据是在前半部分还是后半部，然后在进而取其中部，看其是否找到，然后如果还没找到就一直重复操作，直到找到为止，该算法时间复杂度为O(logn)

代码：

int search(vector<int>& nums, int target) {int l=0,r=nums.size()-1;while(l<=r){int mid=(l+r)>>1;if(nums[mid]<target) l=mid+1;else if(nums[mid]>target) r=mid-1;else return mid;}return -1;}

闭区间：

以左边界为求解的判断状态

int search(vector<int>& nums, int target) {int l=0,r=nums.size()-1;while (l < r){int mid = (l + r + 1) >> 1;if (nums[mid]<=target) l = mid;else r = mid - 1;}return nums[l]!=target?-1:l;}

以右边界为求解的判断状态

//可以用lower_bound()函数代替
int search(vector<int>& nums, int target) {int l=0,r=nums.size()-1;while (l < r){int mid = (l + r) >> 1;if (nums[mid]>=target) r = mid;else l= mid+1;}return nums[r]!=target?-1:r;}