福田做棋牌网站建设哪家技术好,青岛公司注册,网站快速排名优化,哈尔滨网站建设价格低#x1f34e;道阻且长#xff0c;行则将至。#x1f353; #x1f33b;算法#xff0c;不如说它是一种思考方式#x1f340;算法专栏#xff1a; #x1f449;#x1f3fb;123 一、#x1f331;704. 二分查找
题目描述#xff1a;给定一个 n 个元素有序的#xff… 道阻且长行则将至。 算法不如说它是一种思考方式 算法专栏 123 一、704. 二分查找
题目描述给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。来源力扣LeetCode难度简单提示 你可以假设 nums 中的所有元素是不重复的。 n 将在 [1, 10000]之间。 nums 的每个元素都将在 [-9999, 9999]之间。
解题
1.直接查找
直接查找就是for循环没有什么技术点。 2.二分法
题目说明数据是有序不重复故可以直接二分法。 设置指针left、right以及middle 二分的判断条件有两种写法 1.leftright这是一个很自然的写法左右指针交叉之后还没有查找到肯定就不存在目标元素。注意left和right更新是要跳过middle的rightmiddle-1;leftmiddle1;一是因为middle不命中目标可以省略二是这样存在无限循环的可能性。 例如nums {-1,0,3,5,9,12}target 2; 到了第三步将不在变化成为死循环所以不能直接left或right置为middle。正确的更新如下 2.leftright这个判定是认为left不会超过right在上一个的基础上rightright1所以right更新直接使用rightmiddle
主要是区分好搜索的区间。
code: int middle;int left0,right nums.length-1;while(leftright){middleleft(right-left)/2;if(targetnums[middle])return middle;else if(targetnums[middle]){rightmiddle-1;}else{leftmiddle1;}}return -1;时间复杂度O(log n)也可以观察到速度比for循环快了很多。 ☕物有本末事有终始知所先后。 ☝☝☝☝☝我的CSDN☝☝☝☝☝☝
