精选力扣500题第20题 LeetCode 704. 二分查找【c++详细题解】

拼搏现实的明天。 2021-07-24 19:00 325阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、代码

### 1、题目 ###

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

**示例 1:**

输入: nums = [-1,0,3,5,9,12], target = 9
    输出: 4
    解释: 9 出现在 nums 中并且下标为 4

**示例 2:**

输入: nums = [-1,0,3,5,9,12], target = 2
    输出: -1
    解释: 2 不存在 nums 中因此返回 -1

**提示：**

*  你可以假设 `nums`中的所有元素是不重复的。
 *  `n` 将在 `[1, 10000]`之间。
 *  `nums` 的每个元素都将在 `[-9999, 9999]`之间。

### 2、思路 ###

**(二分)** O(logn)

1、在`[l,r]`区间中，`nums[i]`数组具有单调性，因此可以通过二分`>=target`的最左边界找到该值的位置

*  当`nums[mid] >= target`时，往左边区域找， `r = mid`
 *  当`nums[mid] < target`时，往右边区域找，`l = mid + 1`  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

2、若最后找到的元素`nums[r] != target`，则表示不存在该数，返回`-1`，否则返回数值`r`

### 3、代码 ###

class Solution { 
    public:
        int search(vector<int>& nums, int target) { 
          //二分>=x的最左边界
          if(!nums.size()) return -1;
          int  l = 0, r =nums.size() - 1;
          while(l < r)
          { 
              int mid = (l + r) / 2;
              if(nums[mid] >= target) r = mid;
              else l = mid + 1;
          }
          if(nums[r] == target) return r;
          else return -1;
        }
    };

**原题链接：** [704. 二分查找][704.]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/d1f9d171e25149729c1370e02ed3a74e.png
[704.]: https://leetcode-cn.com/problems/binary-search/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/48529c4a05944604967db91dd472a14f.png