理论

二分法作为最基础的搜索逻辑，在我的印象中当时第一次接触这个概念是中学，当时就觉非常神奇，简直是把人类智慧和直觉的象征。接触机器学习，知道了没有免费午餐理论(No free lunch theorem)：
如果我们不对特征空间有先验假设，则所有算法的平均表现是一样的

那就是说二分法在有序数组中的高效性是因为它利用了问题的结构（有序性），而NFL定理告诉我们，如果不考虑问题的特定结构，所有算法的平均性能是一样的。所以，当问题符合某种结构时，针对该结构设计的算法（如二分法）才能优于其他算法，否则可能不如其他方法。例如，在无序数组中，二分法无法使用，可能需要线性查找，这时候NFL定理适用，因为不同算法在不同情况下的表现不同，没有绝对的好坏。

题目

leetcode 704 二分法

思路找到中间值middle=left+(right-left)/2，注意如果是全闭middle在更新的时候+1

C++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        while (left<=right){
            int middle=left+(right-left)/2;
            if(nums[middle]<target){
                left=middle+1;

            }
            else if(nums[middle]>target){
                right=middle-1;
            }
            else return middle;
        }
        return -1;
    }
};

Python

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

leetcode 27 移除

思路是快慢指针
num[fast]!=val-> num[slow]=num[fast];

C++

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n=nums.size();
        int slow=0;
        for(int fast=0; fast<n;fast++){
            if(nums[fast]!=val){
                nums[slow]=nums[fast];
                slow++;
            }
        }
        return slow;
    }
};

Python

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        while val in nums:
            nums.remove(val)
        return len(nums)

原地求解：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        idx = 0
        for num in nums:
            if num != val:
                nums[idx] = num
                idx += 1
        return idx

leetcode 977.有序数组的平方

这里我是认为双指针有些本末导致，感觉这里就是按照先平方再排序最正常，正如nfl中所说，虽然双指针复杂度更低不过我还是更希望code can talk.

C++

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> ans;
        for(int num:nums){
            ans.push_back(num*num);
        }
        sort(ans.begin(),ans.end());
        return ans;
    }
};

Python

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        nums=[num*num for num in nums]
        return sorted(nums)