Leetcode题目链接：704. 二分查找

题目描述：

给定一个 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

解题思路：

二分查找算法

• 算法思路：设置left、right、mid指针分别代表左端点位置、右端点位置、查找元素当前位置，通过判断mid位置元素与左右两边元素的大小关系，更改left或right指针的位置，不断缩小区间直至找到该元素或退出循环条件。

• 左闭右闭写法

  • 初始化边界：left = 0, right = nums.size() - 1

  • 循环条件设置：while(left <= right)

• 左闭右开写法

  • 初始化边界：left = 0, right = nums.size()

  • 循环条件设置：while(left < right)

我的答案：

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

提交结果：

官方答案：

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

作者：力扣官方题解
链接：https://leetcode.cn/problems/binary-search/solutions/980494/er-fen-cha-zhao-by-leetcode-solution-f0xw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。