一、二分查找

  • 704.二分查找 leetcode链接

1.二分查找方法概述

  • 二分查找是针对有序数组的一种查找方式。是利用（letf+right）/2 = mid的方式来对半缩短搜索范围的一种方法，一次查找，搜索的范围就会减半。相较于简单查找找寻一个target需要n步，则二分查找则最多只需查找log2n步。

2.具体实现方法一

点击查看代码
class Solution {    public int search(int[] nums, int target) {        int left = 0;        int right = nums.length -1;        while(left  target){                right = mid -  1;            }else{                left = mid + 1;            }        }        return -1;    }}

方法二

点击查看代码
class Solution {    public int search(int[] nums, int target) {        int left = 0;        right = nums.length;        while (left > 1);            if (nums[mid] == target)                return mid;            else if (nums[mid]  target)                right = mid;        }        return -1;    }}

3.要点总结1.关于length是否-1的问题

  • length是否-1取决于区间是左闭右闭区间（ [ ] ），还是左闭右开区间( [ ) ).当选取左闭右闭区间（ [ ] ）时，length则需要-1，因为搜索区间包含右边界值，即整个数组下标都能取到则length需要-1。如果是左闭右开区间( [ ) )，length则不需要-1，因为右边界值不包含在搜索区间内，右边界值的取值无意义。

2.关于循环条件letf是<=还是<的问题

  • 当区间是左闭右闭区间（ [ ] ），left则取<= right。当区间是左闭右开区间( [ ) )时，则不取= 。

3.关于赋值是赋mid的还是mid-1的问题

  • 当区间是左闭右闭区间（ [ ] ）时，mid则需要-1，因为mid包含在有效值区间，已经排除。当区间是左闭右开区间( [ ) )时，mid则不需要-1，因为mid的值不包含在有效的搜索区间内，无需排除，所以无需-1。

二、移除元素

  • 27.移除元素leetcode链接

1.方法概述方法一：快慢“指针”法

  • 定义一个fast下标和slow下标，两下标同时从0下标处用来寻找需要删除的val值，fast搜索需要删除的val值，如果fast为需要删除的值则fast++，slow不动，当fast不是需要删除的val值时，证明该值是返回数组中需要的值，将fast的值赋给slow，然后slow++。当fast <数值长度时说明遍历完毕，返回slow下标即为新数组的大小值。

方法一：头尾“指针”交换法（自创）

  • 定义一个头下标start和尾下标end，分别从数组的0下标处和末端下标处进行搜索需要删除的val值。目的是将前排纯在的val值移到数组内的最后。有四种情况，一是start对应值和end对应值相等则end–。二是start对应值和end对应值都不相等则start++。三是当satrt的对应值不是val而end的对应值是val的时候，end–，start++。最后当start的对应值等于val的时且end的值不等于val值时，进行数值交换。最终start对应值就是新数组的长度。

2.具体实现方法一

点击查看代码
class Solution {    public int removeElement(int[] nums, int val) {        int n = nums.length;        int left = 0;        for (int right = 0; right < n; right++) {            if (nums[right] != val) {                nums[left] = nums[right];                left++;            }        }        return left;    }}

方法二

点击查看代码
class Solution {    public int removeElement(int[] nums, int val) {         int start = 0;        int end = nums.length-1;        while(start <= end){            if(nums[start] == val &&  nums[end] != val ){                int tmp = nums[start];                nums[start] = nums[end];                nums[end] = tmp;                start++;                end--;            } else if (nums[start] != val && nums[end] == val  ) {                end--;                start++;            }else if(nums[start] != val && nums[end] != val ){                start++;            }else{                end--;            }        }        return start;    }     }

3.要点总结

  • 首先需要明白的时数组的相关知识，如数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。然后重点是双指针的思想方法。

仅供个人参考，欢迎批评指正！