算法——二分查找
介绍二分查找是一个高效的查找算法，查找算法还有线性查找，它的时间复杂度为 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 == 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 == target) {
return mid;
} else if (nums < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]