目錄
1.概論
2.樸素的二分算法
3.求左端點的二分算法和求右端點的二分算法
4.總結
1.概論
要想了解什么是二分算法，我們就要知道什么是二分算法，二分算法是根據數組的規律，每次查找的數據原來的效率可能要O（n）,而我們可以把它優化為logN,這會大大提高我們的算法效率，總的來說我們的二分算法就是通過利用數組的規律來優化效率的一種算法下面我們把二分算法進行分類：1.樸素的二分算法。2.查找左端點的二分算法。3.查找右端點的二分算法。
下面我們遵循從簡到難得規律來進行講解，幫助大家和我一起來認識二分算法。
2.樸素的二分算法
我們空說的話比較抽象，我們直接借助題目來認識二分算法。
力扣704二分查找正好合適。
看到題目，讓我們在數組中讓我們去找一個目標值，我們很容易想到遍歷數組，找到targe進行返回，但是它遍歷數組時間復雜度較高，我們發現我們沒有利用數組有序的規律，所以我們進行算法優化，我們每次求中間的值，讓它跟target進行比較，等于返回找到，小的話讓left=mid+1,大的話讓right=mid-1.我們觀察這個算法我們發現我們每次都會干掉一半的值，時間復雜度會優化到LOGN，這時候有同學就要問了：主播主播，為什么我們每次找中點呢？不能每次找三分之一點，四分之一點，五分之一點嗎？當然可以，只是經過數學大牛的計算證明，發現每次求中點的效率最高，所以我們這里只需要記住我們一般每次干掉一半即可。
下面給出我們的代碼實現：
int search(vector<int>& nums, int target) {int left=0;int right=nums.size()-1;while(left<=right){int mid=left+(right-left)/2;if(nums[mid]>target){right=mid-1;}else if(nums[mid]<target){left=mid+1;}else return mid;}return -1;}3.求左端點的二分算法和求右端點的二分算法
下面我們再來一道題目，來講解我們的二分算法的進階。
這道題我們發現它讓我們求一個范圍，所以我們需要求出左右的范圍，這里我們就要進行分析了，怎么樣求呢？
經過這道題目的分析，我們也是很容易想到的暴力解法就是遍歷數組進行求解，時間復雜度同樣達到了O（n），那么我們接下來進行算法優化，抽象出來數組，主播的字比較難看，湊合著看吧。。。
我們發現我們求出最左節點我們就是要求大于等于的最左節點，注意我們只能求它們邊界的節點，這決定了我們必須得這樣劃分數組。
舉個反例：
我們這里只能求小于等于的最右點解，求不出小于等于中小框范圍的最左節點，這是我們算法導致的。硬求的話會導致效率降低，所以我們這樣劃分數組。不信我們進行求，就知道為什么不行了，
我們是這樣求的,mid>t,right=mid-1;mid<=t,left=mid;我們發現right進入小框的范圍后，變的就只有left了，我們left不斷的等于mid，會不斷向右靠，講到這里各位靚仔應該明白了吧。
所以我們進行這樣的范圍劃分是右意義的。
還有要注意的細節這里我們當left==right之后我們結束循環，因為如果有符合范圍的值，我們一般是left和right移動到同一個為止上。
第二個要注意的點就是當出現偶數的特殊情況是我們怎么解決：
我們這里對mid的處理就不同了，如果mid=left+(right-left)，它是指向偶數數組中間的靠左邊，這里我們發現求最左節點靠右是正常的。但是相反當mid=left+(right-left+1)/2,mid指向right，就會出現問題，因為我們mid<target,left=mid+1;left向右靠，right=mid，right向左靠，right一直等于mid，陷入死循環，所以程序崩掉了。
我們總的來說我們根據劃分來確定mid怎么搞是>t,<=t的組合，還是>=t,<t的組合，
這樣的情況下我們就是前者的組合，
這樣的組合我們就是后者的組合
，至于求最右端點的解法，我們對求最左節點的方法反過來就可了。
下面給出本題代碼題解供大家理解：
vector<int> searchRange(vector<int>& nums, int target) {int left=0;vector<int>num;int right=nums.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target){left=mid+1;}else{right=mid;}}if(nums.size()!=0&&nums[left]==target){num.push_back(left);}else{num.push_back(-1);}right=nums.size()-1;while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]>target){right=mid-1;}else{left=mid;}}if(nums.size()!=0&&nums[left]==target){num.push_back(left);}else{num.push_back(-1);}return num;}4.總結
要想理解二分算法，需要自己畫圖去理解試錯，總的來說注意一下細節就可以。希望大家都可以學會這種效率算法。
)
