704. 二分查找

解题思路

1.升序数组中，查找数组中target的下标，如果不存在，则返回-1，考察的二分查找算法
2.二分查找算法思想：
定义查找的范围left,right，初始查找范围是整个数组。每次取查找范围的中点 mid，比较 nums[mid] 和 target 的大小，如果相等则mid 即为要寻找的下标，如果不相等则根据 nums[mid] 和 target 的大小关系将查找范围缩小一半
3.判断条件为，left<=right，如果left>right，则返回-1,
4.如果nums[mid]<target，则left=mid+1；
如果nums[mid]>target，则right=mid-1；
如果nums[mid]==target，则返回mid；
5.由于时间每次查找对半，所以时间复杂度为O(logn)，空间复杂度为O(1)

解题遇到的问题

1.终止条件
2.不要理解为递归
3.左右值的记录和互换

后续需要总结学习的知识点

1.无序序列时，用哪种算法效率最高？
2.有序序列时，是否二分查找为效率最高？

##解法1
class Solution {
   public static int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }

        int sum = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int a = 0;
            for (int j = i; j < nums.length; j++) {
                a += nums[j];
                if (a > sum) {
                    sum = a;
                }
            }
        }
        return sum;
    }
}

##解法2
class Solution {
    public static int maxSubArray(int[] nums) {
        int sum = nums[0];
        int pre = 0;
        for (int i = 0; i < nums.length; i++) {
            pre = Math.max(nums[i], pre + nums[i]);
            sum = Math.max(pre, sum);
        }
        return sum;
    }
}