算法——二分查找

介绍

二分查找是一个高效的查找算法，查找算法还有线性查找，它的时间复杂度为                                   O                         (                         n                         )                              O(n)                  O(n)，但二分查找的时间复杂度为                                   l                         o                         g                         (                         n                         )                              log(n)                  log(n)（因为是2分，所以此处的log是以2为底的对数函数）。
注：本文提到的查找都是无重复元素的，要是有重复元素，就比力贫苦了。
线性查找

思想

从数组的头部向尾部遍历，假如找到就返回它的下标，假如遍历完还找不到就返回-1。
代码

1. class Solution {
2.         public int linearSearch(int[] nums, int target) {
3.                 for (int i = 0; i < nums.length; i++) {
4.                         if (nums[i] == target) {
5.                                 return i;
6.                         }
7.                 }
8.                 return -1;
9.         }
10. }

复制代码

二分查找

前提

数组是有序的，一样平常要求数组为升序排列，也就是从小到大排列。
思想

二分查找的核心思想就是分治，分就是将一个题目划分为多个子题目，治就是将最小的子题目办理。比如说有一堆苹果，要想吃完这堆苹果（办理一个大题目），就得先将这堆苹果分成许多堆（将题目划分为子题目），直到每堆只剩一个苹果（划分到了最小的子题目），然后再一个一个地将苹果吃掉（将最小的子题目办理）。
现在理解二分查找，二分查找就是找到升序的数组的中心元素，然后比力中心元素与目标元素的巨细，假如目标元素等于中心元素，则直接返回中心元素的下标；假如目标元素大于中心元素，就去右子区间查找；否则就去左子区间查找。直到找到目标元素或无法再找为止（无法再找指的是区间的长度小于1）。注意，假如数组是降序的，则计谋与此恰好相反。
由于二分查找每次都将待查找区间缩小为上一个待查找区间的一半，所以它的时间复杂度为                                   O                         (                         l                         o                         g                         n                         )                              O(logn)                  O(logn)。
代码

1. class Solution {
2.     public int binarySearch(int[] nums, int target) {
3.         // nums一定要有序，如果没有序，就先使用Arrays.sort(nums);将nums按升序排列
4.         int left = 0, right = nums.length - 1;
5.         while (left <= right) {
6.             int mid = left + (right - left >> 1);
7.             if (nums[mid] == target) {
8.                 return mid;
9.             } else if (nums[mid] < target) {
10.                 left = mid + 1;
11.             } else {
12.                 right = mid - 1;
13.             }
14.         }
15.         return -1;
16.     }
17. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。