Leecode每日一题

/** * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 * * * 示例 1: * * 输入: nums = [-1,0,3,5,9,12], target = 9 * 输出: 4 * 解释: 9 出现在 nums 中并且下标为 4 * */

该题难度，官方定义简单。

题目简单易懂，一维数组求目标值下标，直接上代码

public static int search(int[] nums, int target) {    for(int i = 0; i< nums.length; i++){        if(nums[i] == target) {            return i;        }    }    return -1;}

直接一维数组循环，通过判断，返回下标。如果面试出此道题，真的是简单到了极致，当然，你要是提交这个答案，你的面试也就简单到了极致，可以回家休息啦。

很显然，该题为有序（升序）的整形数组，查找目标值下标，因此需要使用简单的算法：二分法。

public int search(int[] nums, int target) {    int low = 0,high = nums.length -1;    while (low <= high) {        int middle = (high - low) / 2 + low;//        int middle = (high + low) / 2;        if (nums[middle] == target) {            return middle;        } else if (nums[middle] < target) {            low = middle + 1;        } else {            high = middle - 1;        }    }    return -1;}

如上就是一个简单的二分法示例，通过不断地取中，缩小查找范围，因为每次范围缩小一半，因此称为二分查找，大大的提高了算法效率。

注意：（二分法中间值的计算）

二分法中间值的算法，一共包含两种：

int middle = (high - low) / 2 + low;     //算法一int middle = (high + low) / 2;           //算法二

从数学角度来看，算法一的公式整理之后与第二种算法完全相同，并且，算法二看着也更为直观和简洁。但使用二分法都会采用第一种算法，为什么呢？

在某种极端的情况下，算法二存在着数值溢出的风险。大家都知道，int的取值范围为2^32，因此当在极端情况下（high + low）超过int的取值范围，由于java的特性，该值会变为负数。算法会因为数值溢出而产生错误结果。而使用第一种算法就完美地避开了这个问题。

官方题解：

二分查找

class Solution {    public int search(int[] nums, int target) {        int low = 0, high = nums.length - 1;        while (low <= high) {            int mid = (high - low) / 2 + low;            int num = nums[mid];            if (num == target) {                return mid;            } else if (num > target) {                high = mid - 1;            } else {                low = mid + 1;            }        }        return -1;    }}

复杂度分析

时间复杂度：O(log⁡n)，其中 n是数组的长度。空间复杂度：O(1)