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)