代码随想录刷题笔记

作者是一名普通本科大二学生，近期购置了Carl学长的代码随想录。同时我也加入了代码随想录星球，准备按照书上的顺序进行一下算法的学习，大概会保持每天一题的进度。会在CSDN上更新自己的进度，当做打卡，也会写一些反思和总结，希望能提高自己的算法水平。

使用的是leetcode网站进行刷题，leetcode网站有对应的学生会员，有一定的优惠。目前使用的语言是java。因为接下来可能有软件的课，准备熟悉一下这种语言。

题目链接

思路总结：

二分查找，取中间值，然后将数组分成两部分分别查找是否有目标元素

初始想法（失败）：想写一个递归的函数来实现，但是由于leetcode的题目函数限制，我不能传送下标，所以并没有成功，但是这个写法可以当做判断一个数组中是否有相应元素的写法。

class Solution {
    public int search(int[] nums, int target) {
        int mid = nums.length/2;
        if(mid == 0 && nums[mid] != target) {
        	return 0;
        }
        if(nums[mid] > target){
            int temp[] = new int[mid];
            System.arraycopy(nums,0,temp,0,mid);
            return search(temp,target);
        }
        else if(nums[mid] < target){
            int temp2[] = new int[nums.length - mid - 1];
            System.arraycopy(nums,mid + 1,temp2,0,nums.length - mid - 1);
            return search(temp2,target);
        }
        else  {
            return 1;
        }
    }
}

这段代码中，在进行下一次的递归调用前，会把相应的子数组传递给函数，最后的时候，如果要进行判断的数组中只有一个元素，且不是我们要找的target则返回0，若找到则返回1。

思路上与二分查找类似。

}

正确做法，直接对下标进行循环即可，

定义target在一个左闭右闭的区间，在这种情况下left和right相等是有意义的，所以我们的while循环判定条件就是 ,在循环内我们有三种情况。

1. 当 时，我们将left更新为mid + 1，因为所求索引在当前情况下一定比mid要大。
2. 当 target" src="https://latex.codecogs.com/gif.latex?nums%5Bmid%5D%20%3E%20target" />时, 我们将right更新为mid – 1，因为所求索引在当前情况下一定比mid要小。
3. 当 时，我们返回当前的下标mid。

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