二分法

二分法通过每次将搜索区间减半实现效率提高。
二分法使用的前提是数组有序，且数组中无重复的元素。

实践中通过while循环控制循环搜索过程，通过判断数组middle索引处的值大于或小于target的值进行搜索区间的更新。

二分法一般有两种区间定义，根据区间定义的不同，while循环条件和区间更新条件也各有不同，可以从区间在数学定义上的“合法性”进行条件的选择(区间左右边界必须合法，更新后的区间不能重复搜索前一次middle处的值)

题目: 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution_1:
    def search(self, nums: List[int], target: int) -> int:
        #左闭右闭，搜索区间是[left,right]
        left = 0
        right = len(nums) - 1
        while(left<=right):
            middle = int((left+right)/2)
            if(target<nums[middle]):
                right = middle - 1
                continue
            elif(target>nums[middle]):
                left = middle + 1
                continue
            elif(target==nums[middle]):
                return middle

        return -1

class Solution_2:
    def search(self, nums: List[int], target: int) -> int:
        #左闭右开，搜索区间是[left,right)
        left = 0
        right = len(nums)
        while(left<right):
            middle = int((left+right)/2)
            if(target<nums[middle]):
                right = middle
                continue
            elif(target>nums[middle]):
                left = middle + 1 # 注意区间合法性,middle已经搜索过了，不应该再被包含
                continue
            elif(target==nums[middle]):
                return middle

        return -1

数组元素移除

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

暴力解法：双层for循环，第一层循环遍历数组寻找需要移除的值，如果找到，使用第二层循环将元素前移。

#暴力法:
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i, l = 0, len(nums) # l是数组的逻辑(实际)长度
        while i < l:
            if nums[i] == val: # 找到等于目标值的节点
                for j in range(i+1, l): # 移除该元素，并将后面元素向前平移
                    nums[j - 1] = nums[j]
                l -= 1
                i -= 1
            i += 1
        return l

快慢指针法： 思想是遇到需要删除的值时跳过，不放入新数组。快指针用于遍历旧数组，判断元素是否需要放入删除元素后的数组，慢指针用于更新元素。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        # 快慢指针
        fast=0
        slow=0
        for i in range(len(nums)):
            if nums[fast]!=val: # 如果不是需要删除的值，就留下赋给新数组
                nums[slow]=nums[fast]
                slow+=1 # 慢指针更新（仅在满足要求时更新结果数组）
            fast+=1 # 快指针用于遍历元素，所以每次循环都更新
        nums = nums[:slow]
        return slow

有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

双指针法：数组平方后最大的元素在两端，并且越往中间元素值越小，使用左右两个指针遍历数组，对比两个指针指向元素的数值，将较大的值更新到结果数组的右端。

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        #暴力法
        for i in range(len(nums)):
            nums[i] = nums[i]**2

        nums.sort()
        return nums


class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        #双指针法
        for i in range(len(nums)):
            nums[i] = nums[i]**2

        i=0 # 左指针
        j=len(nums)-1 # 右指针
        k=len(nums)-1 # 结果数组指针，因为是升序数组，所以从右边更新数组 
        result=[0]*len(nums) # 结果数组
        while(i<=j): #两个指针逐步向中间移动，直到错开。指向同一个元素是允许的，因为每一个元素都需要遍历到。
            if(nums[i]<nums[j]): #较大的元素更新到结果数组中
                result[k]=nums[j]
                j-=1 # 更新遍历右指针
            else:
                result[k]=nums[i]
                i+=1 # 更新遍历左指针
            k-=1

        return result