个人主页:Lei宝啊
愿所有美好如期而遇
本题题目链接https://leetcode.cn/problems/binary-search/description/
算法原理
二段性,我们发现这个数组可以找到某种规律将其分为两段,不断划分下去,最终可以找到target
图示
我们分段初始是可以任意挑选位置的,也可以分成多段,但是分成两段是最优的。
同时,我们上图的箭头代表的是mid,也就是(left+right)除以2,缩小范围也是根据mid指向位置的大小和target对比后得出的。
我们不提数组有序,我们只说二段性,因为后续的二分查找算法数组即使无序,我们依然可以寻找到某种规律去解决。
代码
class Solution {
public:int search(vector<int>& nums, int target) {int lhs = 0;int rhs = nums.size() - 1;while(lhs <= rhs){int mid = lhs + (rhs - lhs) / 2;if(nums[mid] < target) lhs = mid + 1;else if(nums[mid] > target) rhs = mid - 1;else return mid;}return -1;}
};