算法——二分查找

介绍

二分查找是一个高效的查找算法，查找算法还有线性查找，它的时间复杂度为 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  
二分查找
 
前提
 
数组是有序的，一般要求数组为升序排列，也就是从小到大排列。
 
思想
 
二分查找的核心思想就是分治，分就是将一个问题划分为多个子问题，治就是将最小的子问题解决。比如说有一堆苹果，要想吃完这堆苹果（解决一个大问题），就得先将这堆苹果分成很多堆（将问题划分为子问题），直到每堆只剩一个苹果（划分到了最小的子问题），然后再一个一个地将苹果吃掉（将最小的子问题解决）。
 
现在理解二分查找，二分查找就是找到升序的数组的中间元素，然后比较中间元素与目标元素的大小，如果目标元素等于中间元素，则直接返回中间元素的下标；如果目标元素大于中间元素，就去右子区间查找；否则就去左子区间查找。直到找到目标元素或无法再找为止（无法再找指的是区间的长度小于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 
            int mid = left + (right - left > 1);
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid]