LeetCode数组704.二分查找

描述

704. 二分查找
给定一个 n 个元素有序的&＃xff08;升序&＃xff09;整型数组 nums 和一个目标值 target &＃xff0c;写一个函数搜索 nums 中的 target&＃xff0c;如果目标值存在返回下标&＃xff0c;否则返回 -1。

示例 1:

输入: nums &＃61; [-1,0,3,5,9,12], target &＃61; 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

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

思路一&＃xff1a;

直接爆力解法
时间复杂度&＃xff1a;O(n)
空间复杂度&＃xff1a;O(1)

class Solution {
public:int search(vector<int>& nums, int target) {if(nums.size()&＃61;&＃61;0) return -1; //当输入数组为空则返回-1for(int i&＃61;0;i<nums.size();i&＃43;&＃43;){if(nums[i]&＃61;&＃61;target){return i;}}return -1;}
};


思路二&＃xff1a;二分查找法

class Solution {
public:int search(vector<int>& nums, int target) {if(nums.size()&＃61;&＃61;0) return -1; //当输入数组为空则返回-1int left &＃61; 0;int right &＃61; nums.size()-1; //定义target在[left,right],左闭右闭的区间内while(left<&＃61;right){int mid &＃61; left &＃43; ((right-left)/2); //等价与(left&＃43;right)/2if(nums[mid]<target){ //在右区间中left &＃61; mid &＃43; 1;}else if(nums[mid]>target){ //在左区间中right &＃61; mid -1;}else{return mid;}}return -1;}