内销网站要怎么做,专业网站设计制作优化排名,东莞网站关键词排名,外贸网站建设商家介绍
二分查找是一个高效的查找算法#xff0c;查找算法还有线性查找#xff0c;它的时间复杂度为 O ( n ) O(n) O(n)#xff0c;但二分查找的时间复杂度为 l o g ( n ) log(n) log(n)#xff08;因为是2分#xff0c;所以此处的log是以2为底的对数函数#xff09;。
注…介绍
二分查找是一个高效的查找算法查找算法还有线性查找它的时间复杂度为 O ( n ) O(n) O(n)但二分查找的时间复杂度为 l o g ( n ) log(n) log(n)因为是2分所以此处的log是以2为底的对数函数。
注本文提到的查找都是无重复元素的要是有重复元素就比较麻烦了。
线性查找
思想
从数组的头部向尾部遍历如果找到就返回它的下标如果遍历完还找不到就返回-1。
代码
class Solution {public int linearSearch(int[] nums, int target) {for (int i 0; i nums.length; i) {if (nums[i] target) {return i;}}return -1;}
}二分查找
前提
数组是有序的一般要求数组为升序排列也就是从小到大排列。
思想
二分查找的核心思想就是分治分就是将一个问题划分为多个子问题治就是将最小的子问题解决。比如说有一堆苹果要想吃完这堆苹果解决一个大问题就得先将这堆苹果分成很多堆将问题划分为子问题直到每堆只剩一个苹果划分到了最小的子问题然后再一个一个地将苹果吃掉将最小的子问题解决。
现在理解二分查找二分查找就是找到升序的数组的中间元素然后比较中间元素与目标元素的大小如果目标元素等于中间元素则直接返回中间元素的下标如果目标元素大于中间元素就去右子区间查找否则就去左子区间查找。直到找到目标元素或无法再找为止无法再找指的是区间的长度小于1。注意如果数组是降序的则策略与此恰好相反。
由于二分查找每次都将待查找区间缩小为上一个待查找区间的一半所以它的时间复杂度为 O ( l o g n ) O(logn) O(logn)。
代码
class Solution {public int binarySearch(int[] nums, int target) {// nums一定要有序如果没有序就先使用Arrays.sort(nums);将nums按升序排列int left 0, right nums.length - 1;while (left right) {int mid left (right - left 1);if (nums[mid] target) {return mid;} else if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return -1;}
}
