代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素

tag： #二分 #循环不变量
leetcode 地址：704. 二分查找

代码：

function search(nums: number[], target: number): number {
	let left = 0, right = nums.length - 1
	// 我们假设 target 所在的区间是 [a, b] 左闭右闭
	// 这样当 left === right 的时候是有意义的
	
	while(left <= right) {
		const mid = left + Math.floor((right - left) / 2)
		if(nums[mid] === target) return mid
		if(nums[mid] > target) right = mid - 1
		if(nums[mid] < target) left = mid + 1
	}
	return -1
};

思路解析：
看到有序数组，一般就要想到二分查找
这道题目的关键在于明确循环不变量，而循环不变量一般分为两种：

• 左闭右闭
• 左闭右开

这两种都有一个共同点，那就是左闭

通过循环不变量来确定循环条件中 left 与 right 之间的关系（到底是 left < right 还是 left <= right）

tag： #双指针
leetcode 地址：27. 移除元素

代码：

function removeElement(nums: number[], val: number): number {
    let slowIndex: number = 0, fastIndex: number = 0;
    while (fastIndex < nums.length) {
        if (nums[fastIndex] !== val) {
            nums[slowIndex++] = nums[fastIndex];
        }
        fastIndex++;
    }
    return slowIndex;
};

思路解析：

• 通过两个指针