704.二分查找
題目：
給定一個(gè) n 個(gè)元素有序的（升序）整型數(shù)組 nums 和一個(gè)目標(biāo)值 target ，寫一個(gè)函數(shù)搜索 nums 中的 target桐款，如果目標(biāo)值存在返回下標(biāo)咸这，否則返回 -1。
示例：
輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4
解題思路：
1. 二分法：左閉右閉
二分法使用的前提條件是有序數(shù)組和數(shù)組中無(wú)重復(fù)元素魔眨，在這道題中兩種情況都滿足媳维。
左閉右閉區(qū)間指的是 [left, right]，初始條件包含了左右兩個(gè)端點(diǎn)遏暴，while 里面的判斷條件是 left <= right侄刽。
判斷區(qū)間的時(shí)候要注意：
- 當(dāng) nums[middle] > target 時(shí)，意味著目標(biāo)值小于中點(diǎn)值拓挥，目標(biāo)值位于左區(qū)間唠梨，需要更新右邊界，這里的更新規(guī)則是 right = middle - 1侥啤，因?yàn)樾碌膮^(qū)間不包含中點(diǎn)当叭。
- 當(dāng) nums[middle] < target 時(shí)，同樣的道理盖灸，這里的更新規(guī)則是 left = middle + 1蚁鳖。
代碼如下：
var search = function(nums, target) {
let left = 0;
let right = nums.length - 1;
while(right >= left){
const middle = Math.floor((left+right)/2);
if(nums[middle] > target){
right = middle - 1;
}else if(nums[middle] < target){
left = middle + 1;
}else if(nums[middle] == target){
return middle
}
}
return -1;
};
2. 二分法：左閉右開
更多情況下，會(huì)考慮左閉右開區(qū)間赁炎，這指的是 [left, right)醉箕，初始條件包含了左端點(diǎn)為0，右端點(diǎn)為邊界+1徙垫，while 里面的判斷條件是 left < right讥裤。
判斷區(qū)間的時(shí)候?qū)τ诟掠叶它c(diǎn)的情況，即 nums[middle] > target 姻报，這里會(huì)調(diào)整成 right = middle己英，這是因?yàn)橛叶它c(diǎn)是開區(qū)間，可以在范圍內(nèi)吴旋。
代碼如下：
var search = function (nums, target) {
let left = 0;
let right = nums.length;
while (right > left) {
let middle = left + ((right - left) >> 1)
if (nums[middle] > target) {
right = middle;
} else if (nums[middle] < target) {
left = middle + 1;
} else if (nums[middle] === target) {
return middle;
}
}
return -1;
};
注意點(diǎn)：
- 兩種方法在取初始端點(diǎn)损肛、判斷while條件、循環(huán)內(nèi)取左右端點(diǎn)時(shí)遵循 循環(huán)不變量 原則荣瑟，每一次的邊界處理都需要按照區(qū)間來(lái)判斷治拿。
- 取中點(diǎn)的時(shí)候一方面可以考慮位運(yùn)算，>> 1 相當(dāng)于 ? 2笆焰，速度會(huì)更快劫谅，另一方面 left + right 相加可能會(huì)數(shù)字過(guò)大需要處理一下。
27. 移除元素
題目：
給你一個(gè)數(shù)組 nums 和一個(gè)值 val，你需要 原地 移除所有數(shù)值等于 val 的元素同波，并返回移除后數(shù)組的新長(zhǎng)度鳄梅。
不要使用額外的數(shù)組空間叠国，你必須僅使用 O(1) 額外空間并原地修改輸入數(shù)組未檩。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素粟焊。
示例 1:
給定 nums = [3,2,2,3], val = 3, 函數(shù)應(yīng)該返回新的長(zhǎng)度 2, 并且 nums 中的前兩個(gè)元素均為 2冤狡。
你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
解題思路：
1. 暴力解法
這種解法只需要兩層for循環(huán)即可项棠，外層遍歷數(shù)組元素悲雳，內(nèi)層更新數(shù)組，代碼如下：
var removeElement = function (nums, val) {
let size = nums.length;
for (let i = 0; i < size; i++) {
if (nums[i] === val) {
for (let j = i + 1; j < size; j++) {
nums[j - 1] = nums[j]
}
i--;
size--;
}
}
return size;
};
2. 雙指針
這里需要明確的是快慢指針的作用香追，通過(guò)兩個(gè)指針可以在O(n)的時(shí)間復(fù)雜度下解決問(wèn)題合瓢。
- 快指針：尋找新數(shù)組的元素
- 慢指針：記錄新數(shù)組的下標(biāo)位置
代碼如下：
var removeElement = function (nums, val) {
let slow = 0;
let fast = 0;
while (fast < nums.length) {
if (nums[fast] !== val) {
nums[slow++] = nums[fast];
}
fast++
}
return slow;
};
3. 相向雙指針?lè)?/h3>
由于題目不要求順序保持不變，因此可以讓指針從端點(diǎn)開始透典，左側(cè)尋找和val相同的數(shù)晴楔，找到后把右側(cè)的值向前挪，然后右側(cè)指針前移峭咒，沒(méi)找到左側(cè)指針后移税弃。
代碼如下：
var removeElement = function (nums, val) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
if (nums[left] === val) {
nums[left] = nums[right--];
} else {
left++;
}
}
return left;
};
