代码随想录打卡

待我称王封你为后i 2024-02-22 09:14 38阅读 0赞

## 一、二分查找简介 ##

【[二分查找算法简介][Link 1]】

## 二、二分查找算法实现 ##

### 1.左闭右闭写法 ###

java

复制代码

`// 定义左指针 int left = 0; // 定义右指针,由于左闭右闭，所以取nums.length - 1 int right = nums.length - 1; // 当左指针小于等于右指针时执行循环体 while (left <= right) { // 防止溢出 // 定义中间位置取中间值 int middle = left + ((right - left) / 2); // 当目标值大于中间值时，更新左指针,右移左指针缩减范围 // 由于左闭右闭，所以左指针要middle的下一个值 if (target > nums[middle]) { left = middle + 1; } else if (target < nums[middle]) { // 当目标值小于中间值时，更新右指针,左移右指针移缩减范围 // 由于左闭右闭，所以右指针要取middle的上一个值 right = middle - 1; } else { // 当目标值等于中间值时，将其直接返回 return middle; } } // 当左指针大于右指针，说明没有找到目标值，返回-1 return -1;`

### 2. 左闭右开写法 ###

java

复制代码

`// 定义左指针 int left = 0; // 定义右指针，由于左闭右开，所以取nums.length int right = nums.length; // 当左指针小于等于右指针时执行循环体 while (left < right) { // 防止溢出 // 定义中间位置取中间值 int middle = left + ((right - left) >> 1); // 当目标值大于中间值时，更新左指针,右移左指针缩减范围 // 由于左闭右闭，所以左指针要取middle的下一个值 if (target > nums[middle]) { left = middle + 1; } else if (target < nums[middle]) { // 当目标值小于中间值时，更新右指针,左移右指针移缩减范围 // 由于左闭右开，所以右指针可以直接取middle，因为middle不包含在范围内 right = middle; } else { // 当目标值等于中间值时，将其直接返回 return middle; } } // 当左指针大于右指针，说明没有找到目标值，返回-1 return -1;`

## 三、例题 ##

### 1. Leetcode 704 二分查找 ###

1.题目 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = \[-1,0,3,5,9,12\], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = \[-1,0,3,5,9,12\], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1

提示：

*  你可以假设 nums 中的所有元素是不重复的。
 *  n 将在 \[1, 10000\]之间。
 *  nums 的每个元素都将在 \[-9999, 9999\]之间。

来源：力扣（LeetCode） 链接：[leetcode.cn/problems/bi…][leetcode.cn_problems_bi]

1.  解题思路 【[代码随想录网站][Link 2]】
2.  代码实现

*  左闭右闭写法

java

复制代码

`class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while(left <= right) { int middle = (left + right) / 2; if(target > nums[middle]) { left = middle + 1; } else if(target < nums[middle]){ right = middle - 1; } else { return middle; } } return -1; } }`

*  左闭右开写法

java

复制代码

`class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length; while (left < right) { int middle = left + ((right - left) / 2); if (target > nums[middle]) { left = middle + 1; } else if (target < nums[middle]) { right = middle; } else { return middle; } } return -1; } }`

*  调用API

java

复制代码

`class Solution { public int search(int[] nums, int target) { int res = Arrays.binarySearch(nums, target); if(res < 0){ return -1; } return res; } }`

### 2. Leetcode 27 移除元素 ###

1.  题目

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

> // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝 int len = removeElement(nums, val)
> 
> // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) \{ print(nums\[i\]); \}

示例 1：

输入：nums = \[3,2,2,3\], val = 3 输出：2, nums = \[2,2\] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = \[2,2,3,3\] 或 nums = \[2,2,0,0\]，也会被视作正确答案。

示例 2：

输入：nums = \[0,1,2,2,3,0,4,2\], val = 2 输出：5, nums = \[0,1,4,0,3\] 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

*  0 <= nums.length <= 100
 *  0 <= nums\[i\] <= 50
 *  0 <= val <= 100

来源：力扣（LeetCode） 链接：[leetcode.cn/problems/re…][leetcode.cn_problems_re]

1.  解题思路 【[代码随想录网站][Link 3]】
2.  代码实现

*  暴力解法

java

复制代码

`class Solution { public int removeElement(int[] nums, int val) { int length = nums.length; for (int i = 0; i < length; i++){ if (nums[i] == val){ for (int j = i + 1; j < length; j++){ nums[j - 1] = nums[j]; } i--;//这点需要注意，因为下标i以后的数值都向前移动了一位，所以i也向前移动一位 length--; } } return length; } }`

*  双指针

java

复制代码

`class Solution { public int removeElement(int[] nums, int val) { // 快慢指针 int slowIndex = 0; for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) { if (nums[fastIndex] != val) { nums[slowIndex] = nums[fastIndex]; slowIndex++; } } return slowIndex; } }`

作者：东离与糖宝  
链接：https://juejin.cn/post/7232227831114727480  
来源：稀土掘金  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[Link 1]: https://link.juejin.cn?target=https%3A%2F%2Fblog.csdn.net%2Fqq_45978890%2Farticle%2Fdetails%2F116094046%3Fops_request_misc%3D%25257B%252522request%25255Fid%252522%25253A%252522168207493616800197027380%252522%25252C%252522scm%252522%25253A%25252220140713.130102334..%252522%25257D%26request_id%3D168207493616800197027380%26biz_id%3D0%26utm_medium%3Ddistribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-116094046-null-null.142%255Ev86%255Einsert_down28%2C239%255Ev2%255Einsert_chatgpt%26utm_term%3D%25E4%25BA%258C%25E5%2588%2586%25E6%259F%25A5%25E6%2589%25BE%26spm%3D1018.2226.3001.4187
[leetcode.cn_problems_bi]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fbinary-search
[Link 2]: https://link.juejin.cn?target=https%3A%2F%2Fwww.programmercarl.com%2F0704.%25E4%25BA%258C%25E5%2588%2586%25E6%259F%25A5%25E6%2589%25BE.html
[leetcode.cn_problems_re]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fremove-element
[Link 3]: https://link.juejin.cn?target=https%3A%2F%2Fwww.programmercarl.com%2F0027.%25E7%25A7%25BB%25E9%2599%25A4%25E5%2585%2583%25E7%25B4%25A0.html