【Leetcode每日一题】二分算法 - 二分查找（17） (难度⭐)

1. 题目解析

Leetcode链接：704. 二分查找

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

核心在于在给定的数组中查找给定的值，然后返回其索引即可。

2. 算法原理

     1. 定义 left 和 right 指针，分别指向数组的左右区间。

     2.找到待查找区间的中间点 mid。然后分三种情况讨论：

•     i. arr[mid] == target：说明正好找到，返回 mid 的值。
•     ii. arr[mid] > target：说明[mid, right] 这段区间都大于 target。因此舍去右边区间，在左边 [left, mid - 1] 的区间继续查找。即让 right = mid - 1，然后重复步骤 2。
•     iii. arr[mid] < target：说明[left, mid] 这段区间的值都小于 target。因此舍去左边区间，在右边 [mid + 1, right] 区间继续查找。即让 left = mid + 1，然后重复步骤 2。

     3. 当 left 与 right 错开时，说明整个区间都没有这个数，返回 -1。

3. 代码编写

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        int mid;
        while(left <= right)
        {
            mid = (left + right)/2;
            if(nums[mid]>target)
            {
                right = mid - 1;
            }
            else if(nums[mid]<target)
            {
                left = mid + 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
};

The Last

嗯，就是这样啦，文章到这里就结束啦，真心感谢你花时间来读。

觉得有点收获的话，不妨给我点个赞吧！

如果发现文章有啥漏洞或错误的地方，欢迎私信我或者在评论里提醒一声~