题解 | #二分查找-I#

题目：二分查找
描述：请实现无重复数字的升序数组的二分查找
给定一个元素有序的（升序）整型数组nums和一个目标值target ，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1
示例1：输入：[-1,0,3,4,6,10,13,14],13，返回值：6
说明：13 出现在nums中并且下标为 6
示例2：输入：[],3，返回值：-1
说明： nums为空，返回-1
示例3：输入：[-1,0,3,4,6,10,13,14],2，返回值：-1
说明：2不存在nums中因此返回-1

解法一：
思路分析：该题中明确规定数组有序且为升序，且题目已经告诉我们用二分法解决问题，所以可以思考二分法的具体运算过程。
——二分法称为折半法，是一种在有序数组中查找特定目标元素的搜索算法，其具体思路为从数组的中间元素开始搜索，如果该元素为目标元素，则搜索过程结束，否则就进入下一个步骤，如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复判断是为目标值，如果在最后一步还是没有找到中间元素，则返回-1，表示找不到目标元素。
实例分析：输入：[-1,0,3,4,6,10,13,14],13
——当目标值为13时，设置两个指针变量i指向第一个元素，j指向最后一个元素，mid表示中间元素，其判断条件主要分为三种：
1、当中间值为目标值时，返回中间值的下标。
2、当中间值大于目标值时，将j = mid - 1，使区域缩小后，再返回步骤1进行判断。
3、当中间值小于目标值时，将i = mid + 1，使区域缩小后，再返回步骤1进行判断。
图片说明
C++核心代码为：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        if(nums.empty())//当数组中没有元素
            return -1;
        if(nums.size() == 1){//当数组中只有一个元素
            if(nums[0] == target)//如果是目标值则返回位置0
                return 0;
            return -1;
        }
        int len = nums.size();//nums数组的长度
        int i = 0;
        int j = len - 1;
        int mid = 0;
        while(i <= j){//循环条件为i始终小于等于j
            mid = i + (j - i)/2;//中间元素
            if(nums[mid] == target){//是否等于目标值
                return mid;
            }
            if(nums[mid] > target)//大于目标值，说明目标值小，在中间值的左边
                j = mid - 1;
            else{//否则在中间值的右边
                i = mid + 1;
            }
        }
        return nums[mid] = target ? mid : -1;
    }
};

Python核心代码为：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def search(self , nums , target ):
        # write code here
        if not nums:
            return -1
        low, high = 0, len(nums)-1#分别设定首尾指针
        while low <= high:
            mid = int((low + high) / 2)
            if nums[mid] == target:#为目标值的话就返回地址
                return mid
            elif nums[mid] > target:#找左边
                high = mid - 1
            else:#找右边
                low = mid + 1
        return -1

述程序采用二分法进行判断，所以其时间复杂度为 $O(logN)$ ，没有采用任何辅助的内存空间，所以其空间复杂度为 $O(1)$ 。

解法二：
思路分析：既然题目已经规定了使用二分法解决问题，那么除了二分法，我们还可以使用什么方法呢，答案就是顺序法，下面我们用顺序法进行分析，使用一个指针外加一个if语句便可以轻松解决。
既然上面用了python和C++，下面我们用java写出。
Java核心代码为：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        int len = nums.length;//nums数组的长度
        for(int i = 0;i < len;i++){
            if(nums[i] == target){
                return i;//返回该位置
            }
        }
        return -1;
    }
}

——该方法需要遍历元素进行判断，当遍历到目标元素值时，停止，返回其下标，所以其平均时间复杂度为 $O(N)$ ，没有构造任何的辅助内存空间，所以其空间复杂度为 $O(1)$ 。