介紹

二分查找是一個(gè)高效的查找算法，查找算法還有線性查找，它的時(shí)間復(fù)雜度為$O(n)$，但二分查找的時(shí)間復(fù)雜度為$log(n)$（因?yàn)槭?分，所以此處的log是以2為底的對(duì)數(shù)函數(shù)）。

注：本文提到的查找都是無重復(fù)元素的，要是有重復(fù)元素，就比較麻煩了。

線性查找

思想

從數(shù)組的頭部向尾部遍歷，如果找到就返回它的下標(biāo)，如果遍歷完還找不到就返回-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;}
}

二分查找

前提

數(shù)組是有序的，一般要求數(shù)組為升序排列，也就是從小到大排列。

思想

二分查找的核心思想就是分治，分就是將一個(gè)問題劃分為多個(gè)子問題，治就是將最小的子問題解決。比如說有一堆蘋果，要想吃完這堆蘋果（解決一個(gè)大問題），就得先將這堆蘋果分成很多堆（將問題劃分為子問題），直到每堆只剩一個(gè)蘋果（劃分到了最小的子問題），然后再一個(gè)一個(gè)地將蘋果吃掉（將最小的子問題解決）。

現(xiàn)在理解二分查找，二分查找就是找到升序的數(shù)組的中間元素，然后比較中間元素與目標(biāo)元素的大小，如果目標(biāo)元素等于中間元素，則直接返回中間元素的下標(biāo)；如果目標(biāo)元素大于中間元素，就去右子區(qū)間查找；否則就去左子區(qū)間查找。直到找到目標(biāo)元素或無法再找為止（無法再找指的是區(qū)間的長度小于1）。注意，如果數(shù)組是降序的，則策略與此恰好相反。

由于二分查找每次都將待查找區(qū)間縮小為上一個(gè)待查找區(qū)間的一半，所以它的時(shí)間復(fù)雜度為$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;}
}