数组理论基础：****************************************************************************************

C++数组内存地址连续，Java数组寻址交给虚拟机。

704.二分查找

mid=(left+right)>>1的含义

右移运算符>>,运算结果正好能对应一个整数的二分之一值，这就正好能代替数学上的除2运算，但是比除2运算要快。

mid=(left+right)>>1相当于mid=(left+right)/2

也可写成：  int mid =left + ((right-left)>>1);

计算中点：

在二分查找算法中，计算中点的正确公式是： mid = left + (right - left) / 2 这个公式用于计算 left 和 right 之间的中点，下面是详细解释： 公式解释： left + (right - left) / 2 实际上是 (left + right) / 2 的一种避免溢出的方式。 这里，right - left 计算了 left 和 right 之间的距离，然后 (right - left) / 2 计算了这个距离的一半。 将这一半的距离加到 left 上，可以得到 left 和 right 的中点。 防止溢出： 当 left 和 right 的值非常大时，直接使用 (left + right) / 2 可能会导致溢出。特别是在整数范围有限的编程语言中，这种溢出是比较常见的问题。 使用 left + (right - left) / 2 避免了直接将 left 和 right 相加，从而减小了溢出的风险，因为 right - left 的值通常比 left 和 right 的和要小得多。 示例 假设 left 为 2^31-1（即最大的 32 位整数），right 也是 2^31-1。如果直接计算 (left + right) / 2，会导致整数溢出： left + right = 2 * (2^31-1) = 2^32-2，这超出了 32 位整数的范围。 但如果使用 left + (right - left) / 2： right - left = 0 (right - left) / 2 = 0 left + (right - left) / 2 = 2^31-1 不会导致溢出，因为 right - left 不会大到超出整型范围。

left = 0,right = 6,mid = 3

left = 0,right = 2,mid = 1

left = 1,right = 2,mid = 1

left = 0,right = 1,mid = 1;

left = 0,right = 0,mid = 0;

int search(vector<int>& nums, int target) {
        // 数组有序，使用二分查找,左闭右开确定边界
        int length = nums.size();
        // 数组只有一个元素的特殊情况
        if (length == 1) {
            if(nums[0] == target) {
                return 0;
            }
            else {
                return -1;
            }
        }

        // 每次中值取左,(6、7都是3)
        int mid = length/2;
        int left = 0,right = length-1;

        int index = -1;
        while(left <= right) {

            if( nums[mid] == target) {
                index = mid;
                break;
            }
            else if (nums[mid] > target) {
                // 取左侧的区间,左闭右开
                right = mid - 1;
                mid = (left+right)/2;
            }
            else {
                // 当前值小于target,取右侧的区间，左闭右开
                left = mid;
                mid = (left + right)/2;
            }
            
            // 排除特殊情况
            if(right == left + 1) {
                if(nums[left] == target) {
                    return left;
                }
                break;
            }
        }

        return index;

    }

0 1 2 3 4 5 ，target = 5

left = 0,right = 6,mid = 3

left = 3,right = 6,mid = 4

left = 4,right = 6,mid = 5(可以

0 1 2 3 4 5 ，target = 0

left = 0,right = 6,mid = 3

left = 0,right = 3,mid = 1

left = 0,right = 1,mid = 0(可以

0 1 2 3 4 5 ，target = 6

left = 0,right = 6,mid = 3

left = 3,right = 6,mid = 4

left = 4,right = 6,mid = 5

left = 5,right = 6,mid = 5

0 1 2 3 4 5 ，target = -1

left = 0,right = 6,mid = 3

left = 0,right = 3,mid = 1

left = 0,right = 1,mid = 0

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 数组有序，使用二分查找,左闭右开确定边界
        int length = nums.size();
        // 数组只有一个元素的特殊情况
        if (length == 1) {
            if(nums[0] == target) {
                return 0;
            }
            else {
                return -1;
            }
        }

        // 每次中值取左,(6、7都是3)
        int mid = length/2;
        int left = 0,right = length;
        int index = -1;

        do {

            if( nums[mid] == target) {
                index = mid;
                break;
            }
            else if (nums[mid] > target) {
                // 取左侧的区间,左闭右开
                right = mid;
                mid = (left+right)/2;
            }
            else {
                // 当前值小于target,取右侧的区间，左闭右开
                left = mid;
                mid = (left + right)/2;
            }

        } while(left <= right-1)


        return index;

    }
};

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 数组有序，使用二分查找,左闭右开确定边界
        int length = nums.size();
        // 数组只有一个元素的特殊情况
        if (length == 1) {
            if(nums[0] == target) {
                return 0;
            }
            else {
                return -1;
            }
        }


        int left = 0,right = length;
        int index = -1;

        while(left<right) {
            int mid =left + ((right-left)>>1);

            if( nums[mid] == target) {
                index = mid;
                break;
            }
            else if (nums[mid] > target) {
                // 取左侧的区间,左闭右开
                right = mid;
            }
            else {
                // 当前值小于target,取右侧的区间，左闭右开,注意当前的mid不会再取到，因此left需要由mid+1
                left = mid + 1;
            }

        } 


        return index;

    }
};

27.移除元素

注意读题，返回的是不等于target的值。双指针法

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 暴力：新建数组，遍历旧数组，修改新数组
        // 双指针，左指针保存当前数组位置，右指针保存探索位置
        int left = 0,right = 0;
        int result = 0;
        while(right < nums.size()) {
            if (nums[right] != val) {
                // 保留当前的数值,并且给nums[left]赋值
                nums[left] = nums[right];
                left ++;
                right ++;
            } else {
                result ++;
                right ++;
            }
        }
        return nums.size() - result;
    }
};

977.有序数组的平方

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res;
        int left = 0,right = nums.size()-1;

        while (left <= right){
            // 两个指针向中间靠拢,先插大值，再插小值
            if (abs(nums[left]) >= abs(nums[right]) ){
                res.push_back( pow(nums[left],2));
                left++;
            } else{
                res.push_back( pow(nums[right],2));
                right --;
            }
        }

        reverse(res.begin(),res.end());

        return res;
    }
};