704 二分查找
题目链接：力扣
思路：
查找目标值的方法有很多种，根据数据的关系和题目的要求选择最合适的查找方法，才能让查找更加高效
这道题目的介绍到——“有一个有序无重复元素的数组”，其中有两个条件：1).有序 2).无重复
有序才能更好地使用二分法，要不然数据是乱的，没有办法用二分法查；无重复是每一个下标上地值都是唯一的
这两个条件是使用二分查找的条件，遇到这两个前提条件可以考虑一下二分查找
二分查找：
有序的数组，查找某一个值，就是将数组劈成两半，与中间值对比，会出现三种情况：
1).跟中间值相同 —— 就是要找的目标
2).比中间值大 —— 目标值在数组右半边
3).比中间值小 —— 目标值在数组左半边
知道了怎么查找，还有一个细节需要注意：那就是下标的范围，在这里有两种情况：
1).左闭右开
2).左闭右闭
这两种写法的左边都是封闭的，只有右边有两种情况，所以取决于你想不想让右边的下标有意义
左闭右开的写法：
class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length; // 根据左闭右开的原则，right是数组的长度，这个下标是取不到的 while (left < right) { // 每次循环都判断出中间值 int mid = left + ((right - left) >> 1); if ( nums[mid] > target) { // 如果中间值大于目标值，说明目标值在左边，需要继续查找数组的左半边，只需要将右下标移到中间位即可 // right这边是开，是在数组上取不到，mid已经判断过了，不需要再取到，所以给mid贴上right标签 right = mid; } else if (nums[mid] < target) { // 如果中间值小于目标值，说明目标值在右边，需要继续查找数组的右半边，只需要将左下标移到中间位即可 // left这边是闭，是在数组上可以取到的，mid已经判断过了，得在往前上一位 left = mid + 1; } else { // 如果这个中间值是目标值就返回下标 return mid; } } return -1; } }
左闭右闭的写法：
class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 根据左闭右闭原则，在每次查找得过程中，left和right下标位置上的数字都是可以查到的 while (left <= right) { int mid = left + ((right - left) >> 1); if ( nums[mid] > target ) { // 如果中间值大于目标值，说明目标值在左边，需要继续查找数组的左半边，只需要将右下标移到中间位即可 // right这边是闭，是在数组上可以取到的，mid已经判断过了，不需要再取到，所以mid - 1 right = mid - 1; } else if (nums[mid] < target) { // 如果中间值小于目标值，说明目标值在右边，需要继续查找数组的右半边，只需要将左下标移到中间位即可 // left这边是闭，是在数组上可以取到的，mid已经判断过了，得在往前上一位 left = mid + 1; } else { // 如果这个中间值是目标值就返回下标 return mid; } } return -1; } }
27 移除元素
题目：力扣
思路：
说起移除：我们首先想到的是，直接将这个目标删除就可以，但是对于数据来说，删除了元素，后面的元素不会自动补位，所以需要将删除位置后后面得元素整体向前移动一位，就需要再来一次循环，这也是暴力解法
上面的思路是将不要的覆盖/剔除，还有一种就是将要的留下来，使用双指针，可以一个指针在前面检测，另一个指针在后面记录
移除元素
暴力解法：
第一步：遍历数组（外层for循环）
第二步：找到目标值（if判断）
第三步：将目标值后面的数组整体向前移（内层for循环）
第四步：将数组的长度减1；再次循环这个下标
注：这里有一个小细节就是，将后面的数据整体移前之后，这个下标的元素没有判断过，还得再判断一次这个下标
class Solution { public int removeElement(int[] nums, int val) { int size = nums.length; // 从数组的第一个元素开始进行比较 for (int i = 0 ; i < size ; i++) { // 判断是否有元素等于要删除的值 if (nums[i] == val) { // 找到目标值后进行处理，就是怎么将这个元素处理了 // 把后面的数组整体往前移，又是一套循环 for (int j = i; j < size - 1; j++) { nums[j] = nums[j+1]; } i--; // 刚才，这个进if判断的数字的下标上的数字已经被后面的数字覆盖了，要重新进行判断，所以要减一下下标 size--; } } return size; } }
双指针(快慢指针):
这个像是暴力解法的逆向思维：暴力解法是像挤掉我不要的，双指针是像保留下我要的
class Solution { public int removeElement(int[] nums, int val) { int slowIndex = 0; for (int fastIndex = 0 ; fastIndex < nums.length ; fastIndex++) { if (nums[fastIndex] != val) { nums[slowIndex] = nums[fastIndex]; slowIndex++; } } return slowIndex; } }
