查找算法之二分查找
簡單介紹二分查找
二分查找是一種效率較高的查找方法，要求線性表必須采用順序存儲結構，其時間複雜度為O(log2n)
- 二分查找的條件:必須是有序數組
- 二分查找的思想——将目标值和有序數組的中間值進行比較：
當目标值=有序數組中間值時，查找成功；
當目标值<有序數組中間值時，則目标值隻可能在左側，改變右邊界；
當目标值>有序數組中間值時，則目标值隻可能在右側，改變左邊界；
當左右邊界相等時，區間縮成一個點，循環結束，若此時目标值與有序數組中間值仍然不相等，那麼目标值不在有序數組中。
例1、在有序數組中查找目标值
題目
給定一個 n 個元素有序的（升序）整型數組 nums 和一個目标值 target ，寫一個函數搜尋 nums 中的 target，如果目标值存在傳回下标，否則傳回 -1。
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/binary-search
解題思路
鎖定關鍵條件——“升序數組”，那麼在比較nums[i]與目标值target時想到優先采用二分查找法來尋找目标值。
首先定義left和right分為為用于比較的數組的左邊界和右邊界。
每一次都先找到數組範圍的中點mid，比較nums[mid]和target的大小：
- 若nums[mid] = target，則mid為要尋找的小标，傳回mid
- 若nums[mid] > target，則target隻可能在左側，此時右邊界right改變
- 若nums[mid] < target，則target隻可能在右側，此時左邊界left改變
每次進行二分查找都會将查找範圍縮小一半，當left>right時結束查找，即target不在數組中，此時傳回-1。
代碼
class Solution {
public int search(int[] nums, int target) {
/*
定義一個變量left存儲最左邊（最小）的值的下标
同理right存儲最右邊（最大）的值的小标
*/
//由于數組下标是從0開始的，是以right的定義需要-1
int left = 0,right = nums.length - 1;
while (left <= right){
/*
mid為數組最中間的值的下标
mid的定義可以舉例去思考更容易了解
*/
int mid = (right - left)/2 +left;
if (nums[mid] == target){
return mid;
}else if(nums[mid] > target){
/*
由于是升序數組，是以當中間值大于目标值時，
說明目标值隻可能在左側，是以右邊界right發生改變
*/
right = mid -1;
}else {
/*
同理：
由于是升序數組，是以當中間值小于目标值時，
說明目标值隻可能在右側，是以左邊界left發生改變
*/
left = mid +1;
}
}
return -1;
}
}
例2、找出導緻之後所有版本出錯的第一個錯誤版本
題目
你是産品經理，目前正在帶領一個團隊開發新的産品。不幸的是，你的産品的最新版本沒有通過品質檢測。由于每個版本都是基于之前的版本開發的，是以錯誤的版本之後的所有版本都是錯的。
假設你有 n 個版本 [1, 2, …, n]，你想找出導緻之後所有版本出錯的第一個錯誤的版本。
你可以通過調用 bool isBadVersion(version) 接口來判斷版本号 version 是否在單元測試中出錯。實作一個函數來查找第一個錯誤的版本。你應該盡量減少對調用 API 的次數。
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/first-bad-version
解題思路
根據題意，當某個版本為正确版本，則該版本之前所有版本都是正确版本；同理當某個版本為錯誤版本，則該版本之後所有版本都是錯誤版本。抓住這一特性，結合題意要求”盡量減少調用API的次數“，是以我們優先想到二分查找法。
确定左右邊界之後，根據左右邊界計算中間版本，并判斷是否為正确版本：
- 若該版本是正确版本，則第一個錯誤版本肯定在右側，是以左邊界改變
- 若該版本是錯誤版本，則第一個錯誤要麼是該版本要麼在左側，是以右邊界改變
代碼
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
//沒有用數組存儲，是以開始邊界初值為1
int left = 1,right = n;
while (left < right){
int mid = (right - left)/2 +left;
//調用了力扣的接口isBadVersion
if (isBadVersion(mid)){
/*
如果中間版本是錯誤版本，則第一個錯誤要麼
是該版本要麼在左側（具體的還是需要進一步的判斷），
是以右邊界改變
*/
//注意right沒有定義為mid-1,是因為錯誤版本可能就是中間版本
right = mid;
}else {
/*
若中間版本是正确版本，那麼第一個錯誤版本肯定在右側，
是以左邊界改變
*/
left = mid +1;
}
}
//此時left=right,區間為一個點，也就是答案
return right;
}
}
例3、在一個排序數組中搜尋目标值的插入位置
題目
給定一個排序數組和一個目标值，在數組中找到目标值，并傳回其索引。如果目标值不存在于數組中，傳回它将會被按順序插入的位置。
請必須使用時間複雜度為 O(log n) 的算法。
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/search-insert-position
解題思路
同樣的先确定左右邊界，根據左右邊界計算中間下标mid；對nums[mid]和target進行比較：
- 若相等，則傳回下标mid;
- 若nums[mid]<target，則左邊界left右移；
- 若nums[mid]>target，則右邊界right左移；
假設插入位置為pos，那麼nums[pos-1]<target<=nums[pos]（因為target有可能比所有的值都大，此時要插入在最右側，是以存在等于關系），題意可以簡化為”在一個有序數組中找第一個大于等于target的下标“，是以同樣可以使用二分查找法。
代碼
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
/*
ans初值設定為數組長度可以省略邊界條件的判斷，
以為存在一種情況是target大于數組中的所有數，
此時需要插入到數組長度的位置
*/
int left = 0,right = n-1,ans = n;
/*
當你插入進去後，目标值也就成為了nums[pos],
是以nums[pos]<=target<nums[pos+1]也是可以的
*/
while (left <= right){
int mid =((right - left) >>1) +left;
if (target <= nums[mid]){
ans = mid;
right = mid -1;
}else {
left = mid +1;
}
}
return ans;
}
}
注意：
java中<<、>>、>>>三種移位運算符：