二分法（注意區(qū)間）
- 給定一個 n 個元素有序的（升序）整型數(shù)組 nums 和一個目標(biāo)值 target ，寫一個函數(shù)搜索 nums 中的 target贮乳，如果目標(biāo)值存在返回下標(biāo)，否則返回 -1胀屿。
題目鏈接：https://leetcode.cn/problems/binary-search/
文章講解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
視頻講解：https://www.bilibili.com/video/BV1fA4y1o715
思路
理解二分法利用區(qū)間檢索的概念
區(qū)間的定義一般為兩種塘揣，左閉右閉即[left, right]包雀，或者左閉右開即[left, right)宿崭。
1. 左閉右閉
- 檢索區(qū)間：循環(huán)檢索[left, right]，每次循環(huán)都會檢索一次left 或者 right(取決于target和mid的大小關(guān)系)才写。
-
關(guān)鍵點
1葡兑、存在[1,1] left=right的情況奖蔓，所以while(l<=r)
2、每次都會檢索left 或者right讹堤，下一個循環(huán)不必再檢索 上一次的left 或right了吆鹤。（r=mid-1 或者 l=mid+1就是防止再次檢索）
此例檢索了right
//左閉右閉
public static int searchIncludeLR(int[] nums, int target) {
int l=0;
int r=nums.length-1;
int mid;
// 避免當(dāng) target 小于nums[0] nums[nums.length - 1]時多次循環(huán)運算
if(target<nums[0]&&target>nums[nums.length-1]){
return -1;
}
while(l<=r){
// >>優(yōu)先級較低 所以要再加 ()
mid = l + ((r-l)>>1);
//mid=(r+l)/2;
System.out.println("LR=====l:"+l+"mid:"+mid+"r:"+r+"target:"+target);
if(target<nums[mid]){
r=mid-1;
}else if(target>nums[mid]){
l=mid+1;
}else if (target==nums[mid]){
return mid;
}
}
return -1;
}
2. 左閉右開
- 檢索區(qū)間：循環(huán)檢索[left, right)，每次可能檢索一次left 洲守，但是不檢索right疑务。
- 關(guān)鍵點
1、因為不存在[1,1)的情況梗醇，所以while(l<r)
2知允、左閉只考慮left下次不檢索問題 ,所以left=mid+1
3、因為右開叙谨，所以每次都不會檢索到right, 所以初始right =nums.length
//左閉右開
public static int searchIncludeL(int[] nums,int target){
int l=0;
int r=nums.length;
int mid;
if(target<nums[0]&&target>nums[nums.length-1]){
return -1;
}
while(l<r){
// >>優(yōu)先級較低 所以要再加 ()
mid = l + ((r-l)>>1);
//mid=(r+l)/2;
System.out.println("L=====l:"+l+"mid:"+mid+"r:"+r+"target:"+target);
if(target<nums[mid]){
r=mid;
}else if(target>nums[mid]){
l=mid+1;
}else if(target == nums[mid]){
return mid;
}
}
return -1;
}
雙指針
- 給你一個數(shù)組 nums 和一個值 val温鸽，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度手负。
不要使用額外的數(shù)組空間涤垫，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。
元素的順序可以改變竟终。你不需要考慮數(shù)組中超出新長度后面的元素蝠猬。
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/remove-element
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)衡楞，非商業(yè)轉(zhuǎn)載請注明出處吱雏。
題目鏈接：https://leetcode.cn/problems/remove-element/
文章講解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
視頻講解：https://www.bilibili.com/video/BV12A4y1Z7LP
方法一：暴力破解法
//暴力破解法，雙循環(huán)
public static int removeElement(int[] nums, int val) {
System.out.println(nums.length);
int r=nums.length;
for(int i=0;i<r;i++){
if(nums[i]==val){
for(int j=i;j<r-1;j++){
nums[j]=nums[j+1];
}
r=r-1;
i=i-1;
}
}
return r;
}
方法二：雙指針瘾境，快慢指針
雙指針法（快慢指針法）： 通過一個快指針和慢指針在一個for循環(huán)下完成兩個for循環(huán)的工作歧杏。同時for循環(huán)
- 定義快慢指針
快指針：尋找新數(shù)組的元素 ，新數(shù)組就是不含有目標(biāo)元素的數(shù)組
慢指針：指向更新 新數(shù)組下標(biāo)的位置【如果是val值那么就不更新迷守，所以就可以不移動】
public static int doubleE(int[] nums,int val){
int slow=0;
for (int fast = 0; fast <nums.length ; fast++) {
if(nums[fast]==val){
//slow=fast是錯誤的犬绒，
//正確是什么都不做，遇到val==快指針的不更新
//slow=fast;
}else{
nums[slow]=nums[fast];
slow++;
}
}
return slow;
}
