二分查找--二分查找算法(朴素二分模板)

个人主页：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;
    }
};