算法学习笔记3 寻找数组的中心索引
鱼友9113
2023-09-28 19:42
阅读2673
https://leetcode.cn/leetbook/read/array-and-string/yf47s/ （篇幅有限，引用一下leetcode~）
题解思路：本题这种情况，可以使用二分查找法
一个问题待查找的是整数，并且范围已知的情况下
解释一下二分法
1 首先我们先定义一些需要用到的变量：
数组nums[]:有序排列（前提条件）
left：代表数组左侧元素的下标和最终返回的将target插入的下标，初始值为0（第一个元素）
right：代表数组右侧元素的下标，初始值为数组长度-1（最后一个元素）
sum：代表在数组中的中间元素
int mid = left + (right - left) / 2;
，请见图示：以数组[ 1, 3, 5, 6, 8, 2, 10 ]，想找出target元素为2的数组索引为例：
遍历次数 target mid nums[mid] left right
1 2 3 6 0 6
于是：2<6(target<nums[mid]) ，因此right = mid-1=2, 此时mid的下标为：（0+2-0）/2=1，再次遍历：
遍历次数 target mid nums[mid] left right
2 2 1 3 0 2
此时第二次遍历的图示：
于是：2<3(target<nums[mid]) ，因此right = mid-1=0, 此时mid的下标为：0，再次遍历：
遍历次数 target mid nums[mid] left right
3 2 0 1 0 1
于是：2>1(target>nums[mid]) ，因此可以确定可插入的位置是left+1=0+1=1
最终的题解代码：
private int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while (left <= right) {
int mid = (left + (right - left)) / 2;
if (nums[mid] == target) {
return mid; // 目标值已经在数组中，返回索引
} else if (nums[mid] < target) {
left = mid + 1; // 目标值在右半部分
} else {
right = mid - 1; // 目标值在左半部分
}
}
return left; // 目标值不存在于数组中，返回插入位置
}
🤔关于最后返回值，我迷糊了很久，于是乎问了gpt...(太蠢了，莫笑哈😂)
评论
问答助学
相关内容
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
内容推荐
Day 01✅ 今天做了: 系统学习 SpringSecurity⏰ 明天计划:1. 刷 SpringBoot, Spring 相关面试题2. 基于 SpringSecurity 扩展用户中心实现 RBAC 权限管理，控制
2
Day 30✅ 今天做了：看MySQL 面试题⏰ 明天计划：刷Redis 面试题📚 今日感悟：坚持
0
Day 59✅ 今天做了：Vibe Coding学习、leetcode hot100刷题、Python基础知识面试题准备⏰ 明天计划：Vibe Coding学习、leetcode hot100刷题、Python基础知识面试题准备📚 今日感悟：继续加油
2
Day 3，4✅ 做了：看ai八股，python看到第四章⏰ 明天计划：继续看八股和学python📚 今日感悟：
1
day2今天学习了java里switch的使用和格式
2
作者分享
大家好，好久没更新自己的状况了。
经过长时间的gap，现在被以前的公司重新录取做对日驻场项目的开发，仍然是java
考虑到日本项目的技术栈和工作流与国内项目的巨大差异，也穿越幻想，清醒的认知到自己的处境。
今后，会继续持续不断地学习技术与外语（英语和日语），并保持记录的。
记录将发在这里，希望能够和各位老师和大佬们相互学习，多多交流！
2
稍微说点技术之外的一点心得吧。
最近突然发现，貌似忘记自己曾经有过抑郁症了。可能是因为发现想学习的事物太多太多了，除了技术之外还很多别的方面的电子书没看，有人类学，艺术，哲学，神秘学等就很想看。当然这些以后再看哈哈哈，现在就是以技术为主。所以就，有时候想到以前的一些状态反而会觉得平静。明天继续加油[胜利]
21
oj判题系统遇到的问题：当你的Docker Java库无法连接到Docker守护进程的Unix该怎么办？
10
OJ项目遇到的问题（直播里有讲但还是想记录一下）--构建远程项目相关
14
OJ判题系统小问题分享--文件夹权限
10
