二分查找法

1.含義：二分查找算法，也叫折半查找算法。二分查找的思想非常簡單，有點類似分治的思想。二分查找針對的是一個有序的數(shù)據(jù)集合，每次都通過跟區(qū)間的中間元素對比，將待查找的區(qū)間縮小為之前的一半，直到找到要查找的元素，或者區(qū)間縮小為0

2.使用條件:題目強調(diào)數(shù)組中為有序數(shù)組，且無重復元素，因為一旦有重復元素，使用二分查找法返回的元素下標可能不是唯一的。

3.注意要點：邊界條件的控制，二分查找涉及的很多的邊界條件，邏輯比較簡單，但有些東西容易混亂。例如到底是while(left<right)還是while(left<=right)，到底是right=middle呢，還是要right=middle-1？混亂的主要原因是因為對區(qū)間的定義沒有想清楚，區(qū)間的定義就是不變量。要在二分查找的過程中，保持不變量，就是在while尋找中每一次邊界的處理都要堅持根據(jù)區(qū)間的定義來操作，這就是循環(huán)不變量規(guī)則。

4.二分法的區(qū)間定義：二分法的區(qū)間的定義一般分為兩種，左閉右閉即[left,right]，或者左閉右開即[left,right）。

5.二分法的第一種寫法：我們將區(qū)間設定為[left,right]，區(qū)間的定義決定了二分法代碼應該如何寫，定義目標值target在[left,right]區(qū)間有如下兩點：

1.while(left<=right)要使用<=，因為left==right是有意義的，所以使用<= 2.if（nums[middle]>target) right要賦值為middle-1，因為當前這個nums[middle]一定不是target，那么接下來要查找的左區(qū)間結(jié)束下標位置就是middle-1

代碼如下

class solution { public:int search(vector<int> & nums,int target){int left = 0;int right = nums.size()-1;while(left <= right){int middle = (left + right)/2;if(nums[middle] > target){right = middle - 1;}else if(nums[middle] < target){left = middle + 1;}else{return middle;}}return -1;} }

6.二分法的第二種寫法：

定義 目標值target是在一個左閉右開的區(qū)間里，也就是[left,right），那么二分法的處理方式為

1.while(left < right),這里使用<，因為left==right在區(qū)間[left,right）是沒有意義的。 2.if(nums[middle] > target) right 更新為middle，因為當前nums[middle]不等于target，因為尋找區(qū)間是左閉右開區(qū)間，所以right更新為middle，即：下一個查詢區(qū)間不會去比較nums[middle]

代碼如下：

class solution { public:int search(vector<int> &nums,int target){int left = 0;int right = nums.size();while(left < right){int middle = (left + right)/2;if(nums[middle] > target){right = middle;}else if(numms[middle]<target){left = middle + 1;}else{return middle;}}return -1;} }

總結(jié)

以上是生活随笔為你收集整理的浅析二分查找的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。