数组理论基础，704. 二分查找，27. 移除元素
704. 二分查找
最简单的二分思想的应用，主要锻炼写两种方法
两种方法的区别就是：右指针的每次变化，可能还有就是最后找到目标值后的一个下标到底是什么
二分思想：左右边界，固定一个边界，不断移动另一个边界，直到最后边界重叠，也就找到了这个目标值
移动边界的条件是：比较区间的中间值和目标值的大小
class Solution {
public int search(int[] nums, int target) {
//左闭右闭
int lt = 0, rt = nums.length-1;
int mid;
while(lt <= rt){
mid = lt + ( rt - lt ) / 2;
if( nums[mid] == target) return mid;
else if( nums[mid] < target ){
lt = mid + 1;
}else{
rt = mid - 1;
}
}
return -1;
}
}class Solution {
public int search(int[] nums, int target) {
//左闭右开
int lt = 0, rt = nums.length;
int mid;
while(lt < rt){
mid = lt + ( rt - lt ) / 2;
if( nums[mid] == target) return mid;
else if( nums[mid] < target ){
lt = mid + 1;
}else{
rt = mid;
}
}
return -1;
}
}题目建议： 大家能把 704 掌握就可以，35.搜索插入位置 和 34. 在排序数组中查找元素的第一个和最后一个位置 ，如果有时间就去看一下，没时间可以先不看，二刷的时候在看。
先把 704写熟练，要熟悉 根据 左闭右开，左闭右闭 两种区间规则 写出来的二分法。
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
视频讲解：手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili
附一下另外两题 35 34
这个题目其实就是需要多考虑一下，两种方法最后返回的插入下标的区别
就是返回左指针，因为闭合的话一定是右指针在左指针的左边，结束循环没找到，不闭合就是右指针等于左指针，结束循环没找到，所以一定是左指针是插入的下标
class Solution {
public int searchInsert(int[] nums, int target) {
//左闭右闭
int lt = 0, rt = nums.length-1;
int mid;
while ( lt <= rt ) {
mid = lt + ( rt - lt ) / 2;
if( nums[mid] == target ) return mid;
else if ( nums[mid] > target ) {
rt = mid - 1;
} else {
lt = mid + 1;
}
}
return lt;
}
}class Solution {
public int searchInsert(int[] nums, int target) {
//左闭右开
int lt = 0, rt = nums.length;
int mid;
while ( lt < rt ) {
mid = lt + ( rt - lt ) / 2;
if( nums[mid] == target ) return mid;
else if ( nums[mid] > target ) {
rt = mid;
} else {
lt = mid + 1;
}
}
return lt;
}
}34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
这个题目就是比之前的多的是，需要找到两个下标，可以分解为找到开始位置的下标和结束位置的下标，使用两次二分查找，然后问题就是：因为是非递减，存在平台，怎么能找到是个问题；首先来看，我们需要明确的是我们始终需要将左右边界框住我们的目标值，所以判断如何移动左右边界的条件就是，看mid和目标值的位置对比，进行分情况讨论。一般分为小于，等于，大于。
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length == 0) return new int[]{-1,-1};
//左闭右闭，这是需要很多边界条件的
int left, right;
int lt = 0, rt = nums.length-1;
int mid;
while (lt <= rt) {
mid = lt + (rt - lt) / 2;
if (nums[mid] >= target) {
rt = mid - 1 ;
}else {
lt = mid + 1;
}
}
// System.out.println(lt);
if(lt >= 0 && lt < nums.length) left = target == nums[lt] ? lt : -1;
else return new int[]{-1,-1};
if(left == -1) return new int[]{-1,-1};
lt = 0;
rt = nums.length-1;
// int mid;
while (lt <= rt) {
mid = lt + (rt - lt) / 2;
if(nums[mid] <= target) {
lt = mid + 1;
}
else{
rt = mid - 1;
}
}
if(rt < 0 && rt > nums.length) return new int[]{-1,-1};
right = rt;
return new int[]{left, right};
}
}class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length == 0) return new int[]{-1,-1};
//左闭右闭
int left = -2, right = -2;
int lt = 0, rt = nums.length-1;
int mid;
while (lt <= rt) {
mid = lt + (rt - lt) / 2;
if (nums[mid] >= target) {
rt = mid - 1 ;
left = rt + 1;
}else {
lt = mid + 1;
}
}
lt = 0;
rt = nums.length-1;
// int mid;
while (lt <= rt) {
mid = lt + (rt - lt) / 2;
if(nums[mid] <= target) {
lt = mid + 1;
right = lt -1 ;
}
else{
rt = mid - 1;
}
}
System.out.println(left);
System.out.println(right);
//左边界和右边界没有变化的话，就是没有找到
//左边界和有边界的间距如果大于0，则是找到
if ( left == -2 || right == -2 || right - left < 0){
return new int[]{-1, -1};
}
return new int[]{left, right};
}
}27. 移除元素
题目建议： 暴力的解法，可以锻炼一下我们的代码实现能力，建议先把暴力写法写一遍。 双指针法 是本题的精髓，今日需要掌握，至于拓展题目可以先不看。
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
