介绍
二分查找是一个高效的查找算法，查找算法还有线性查找，它的时间复杂度为
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;
}
}
