1. 二分查找

二分查找关键就是循环不变量：区间定义。是左闭右闭还是左闭右开。
初始化，while循环和if条件语句这三部分处理要一致。(之前刷过这个数组方面的题，但是再刷的时候又忘了。)

1.1 左闭右闭

$[left,right]$左右区间的边界都是有意义可以取到的。在初始化的时候$right$就要初始化为num.length-1，然后在循环判断的时候left和right是可以相等的，left和right相等左闭右闭区间中是有值的有效，然后在条件判断的时候，right的更新是middle-1，因为right是可以取到的，middle这个位置上的值明显不等于target，所以为了避免重复，right就取middle-1。

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

class Solution:def search(self, nums: List[int], target: int) -> int:right = len(nums)-1left = 0while(right >= left):mid = int(left+(right-left)/2)if(nums[mid] == target):return midelif(nums[mid]>target):right = mid-1else:left = mid+1return -1

1.2 左闭右开

$[left,right)$区间左边界都是有意义可以取到的，右边界是取不到的。在初始化的时候$right$就要初始化为num.length（因为right取不到，如果赋值为num.length-1就漏掉了最后一个值），然后在循环判断的时候left和right是不能相等的，left和right相等左闭右开区间中没有有效的值，然后在条件判断的时候，right的更新是middle，因为right是不可以取到的。

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

class Solution:def search(self, nums: List[int], target: int) -> int:right = len(nums)left = 0while(right > left):mid = int(left+(right-left)/2)if(nums[mid] == target):return midelif(nums[mid]>target):right = midelse:left = mid+1return -1

2. 移除元素

移除元素用到双指针。
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
主要的思想是定义一个快指针和慢指针，快指针就是找数组中符合条件的值，慢指针指明数组中更新的位置。然后将慢指针位置的值更新为快指针位置的值。

class Solution {public int removeElement(int[] nums, int val) {int remainNums = 0;int i=0,j=0;for(; j < nums.length; j++){//其中j是快指针，i是慢指针if(nums[j] != val){nums[i] = nums[j];i++;}}return i;}
}

class Solution:def search(self, nums: List[int], target: int) -> int:right = len(nums)left = 0# index = -1while(right > left):mid = int(left+(right-left)/2)if(nums[mid] == target):return midelif(nums[mid]>target):right = midelse:left = mid+1return -1

3. 有序数组的平方

有序数组的平方也需要双指针。当时没看题解和视频的时候，自己想的很复杂。
感觉关键一点就是结果数组从后往前更新，双指针一个在最左边一个在最右边，向中间移动。定义一个pos变量指示结果数组更新的位置。更新的时候，比较左右指针的值，获得最大值，将这个最大值赋值给结果数组当前pos位置，然后对应指针向中间移动。每次更新pos–。

class Solution {public int[] sortedSquares(int[] nums) {int n = nums.length;int right = n-1;int left = 0;int pos = n-1;int[] ans = new int[n];while(right>=left){int rightSquare = nums[right]*nums[right];int leftSquare = nums[left]*nums[left];if(rightSquare>leftSquare){ans[pos] = rightSquare;pos--;right--; }else{ans[pos] = leftSquare;pos--;left++;}}return ans;

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:n = len(nums)ans = [0]*ni, j, pos = 0, n-1, n-1while i<=j:if nums[i]*nums[i]>nums[j]*nums[j]:ans[pos] = nums[i]*nums[i]i +=1else:ans[pos] = nums[j]*nums[j]j -=1pos-=1return ans

参考力扣题目、文章、视频

1. https://leetcode.cn/problems/binary-search/
2. https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
3. https://www.bilibili.com/video/BV1fA4y1o715/
4. https://leetcode.cn/problems/remove-element/description/
5. https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
6. https://www.bilibili.com/video/BV12A4y1Z7LP/
7. https://leetcode.cn/problems/squares-of-a-sorted-array/description/
8. https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
9. https://www.bilibili.com/video/BV1QB4y1D7ep/?vd_source=145b0308ef7fee4449f12e1adb7b9de2