算法日記---二分查找

前言

一、二分查找

1.思想

2.簡單二分

3.優點

4.局限性

二、模板

1.基本模板

2.簡單例題（LeetCode）

4.有重復元素的二分

5.0-1問題

總結

前言

本文通過講解簡單的二分查找配合leetcode例題對二分查找本質、模板進行了基礎的總結

提示：以下是本篇文章正文內容，下面案例可供參考

一、二分查找

1.思想

二分查找本質是折半查找思想，每一輪查找的范圍是上一輪的一半，每次查找比較中間元素的值和目標值的大小。比較結論決定去哪一邊作為下一輪的查找范圍，循環直到查找范圍為空。

2.簡單二分

簡單二分指的是數組不包含重復的元素，重點關注每次判邊的邏輯。

3.優點

速度快 O(logn)且不需要額外的空間

4.局限性

有序：需要保證每次折半都有意義
數組：數組尋址的復雜度是 O (1)。如果是用鏈表存儲一串數，二分查找是無意義的。鏈表的尋址是 O (n)。

二、模板

1.基本模板

二分查找的模板很多樣，開閉的條件不同，判斷的條件也不同

最本質的問題是當前判斷結束后，下一次要取左半邊還是右半邊，縮小區間的條件是什么？判斷的條件是什么?

注意：

left<=right:實際進入循環時，left和right只向的元素不會進行if條件判斷。比如left=right時，加此等號，才會對二者所指元素進行判斷。否則不會。
mid =（left+right）>>>1：因為java會把最高位看成符號位，如果兩個數過大，可能會導致數據溢出問題。我們需要通過無符號右移運算符來避免這種問題。還有一種寫法是mid=left+(right-left)/2
更新left和right，避免死循環

public static int binarySerach(int[] a,int target){int left=0;int right=a.length-1;while(left<=right){int mid=(left+right)>>>1;if(target<a[mid]){//目標數在左邊right=mid-1;}else if(a[mid]<target){//目標書在右邊left=mid+1;}else{return mid;}}return -1;
}

2.簡單例題（LeetCode）

1.704. 二分查找(基本簡單)

class Solution {public int search(int[] nums, int target) {int left=0;int right=nums.length-1;while(left<=right){int mid=(left+right)>>>1;if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid-1;}else{return mid;}}return -1;}
}

2.744.尋找比目標字母大的最小字母

class Solution {public char nextGreatestLetter(char[] letters, char target) {int left=0;int right=letters.length-1;while(left<=right){int mid=(left+right)>>>1;if(letters[mid]<=target){left=mid+1;}else{right=mid-1;}}return left<letters.length?letters[left]:letters[0];}
}

3.74. 搜索二維矩陣

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int left=0;//使用m*n將二維轉為一維int m=matrix[0].length;int n=matrix.length;int right=m*n-1;while(left<=right){int mid=(left+right)>>>1;int x=matrix[mid/m][mid%m];//把mid元素轉換回原二維矩陣的位置if(x==target){return true;}else if(x>target){right=mid-1;}else{left=mid+1;}}return false;}
}

4.162. 尋找峰值

此題究其本質依然是二分查找，我們需要根據題目重要條件進行理解

“你可以假設?nums[-1] = nums[n] = -∞?。”

以下做法需要注意邊界情況的判斷

class Solution {public int findPeakElement(int[] nums) {int n = nums.length;if (n == 1) {return 0;}int left = 0, right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;// 邊界情況判斷：數組第一個元素是峰值（只有它自己，或者比下一個大）if (mid == 0) {if (nums[mid] > nums[mid + 1]) {return mid;}}// 邊界情況判斷：數組最后一個元素是峰值（只有它自己，或者比前一個大）else if (mid == n - 1) {if (nums[mid] > nums[mid - 1]) {return mid;}}// 中間位置是峰值（比左右都大）else if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {return mid;}// 判斷峰值在左側還是右側if (nums[mid] < nums[mid + 1]) {// 右側有上升趨勢，峰值在右側left = mid + 1;} else if (nums[mid] < nums[mid - 1]) {// 左側有上升趨勢，峰值在左側right = mid - 1;}}// 理論上不會走到這里，因為題目保證有解return -1;
}}

題解中的做法是無需單獨判斷邊界情況的，也沒有主動對mid元素與左右兩元素進行比較

因為左右邊界都是負無窮，找到往遞增的一邊方向找就一定能找到峰值（圖中白圈內區域）。這就代表著?只要數組中存在一個元素比相鄰元素大，那么沿著它一定可以找到一個峰值。

特點：一分為二后，一側是有序數組，另一側是循環數組。

根據這個特點，先判斷有序數組、循環數組分別在哪一側，再判斷 target 在有序數組還是循環數組中

判斷方法是讓 target 和有序數組的首尾做比較，看是否在有序數組中。

1.?3. 搜索旋轉排序數組

class Solution {public int search(int[] nums, int target) {int left=0;int right=nums.length-1;while(left<=right){int mid=(left+right)>>>1;if(nums[mid]==target){return mid;}//左半部分有序if(nums[left]<=nums[mid]){//目標值在左半部分區間內if(nums[left]<=target && target<nums[mid]){right=mid-1;}else{left=mid+1;//縮小范圍到右半部分區間}}// 右半部分是有序的else {// 目標值在右半部分有序區間內if (nums[mid] < target && target <= nums[right]) {left = mid + 1;} else {right = mid - 1;//縮小范圍到左半部分區間}}}return -1;}}

2.153. 尋找旋轉排序數組中的最小值

不多說了，都在注解里：

最主要的還是需要判斷目標值到底是在mid的左邊還是右邊，才能進行下一步二分。而判斷依據就是根據兩端遞增區間的特性將nums[mid]和nums[right]進行比較。這也就是開篇說的判斷取左半段還是右半段最重要的條件。

class Solution {public int findMin(int[] nums) {int left=0;int right=nums.length-1;while(left<=right){int mid=(left+right)>>>1;//首先由題可知，數組一定被分為了左右兩個遞增區間（或者沒分，也就是0次旋轉），且第一段所有元素大于第二段所有元素//需要比較nums[mid]和nums[right]的關系。//如果<=，意味著nums[mid]一定處于第二個遞增區間，最小值要么是該元素，要么就在該元素左側//如果>，意味著nums[mid]處于第一個遞增區間。最小值一定在該元素右側if(nums[mid]>nums[right]){//mid處于左半段left=mid+1;}else{//mid處于右半段if(mid==0||nums[mid]<=nums[mid-1]){//mid就是最小值,注意mid=0時索引越界問題return nums[mid];}else{//mid處于右半段，但最小值在mid的左邊right=mid-1;}}}return -1;}
}

4.有重復元素的二分

通常要求找出第一個目標元素或是最后一個目標元素

存在重復元素的二分查找，無非就是多加了一個判斷，判斷是否為第一個/最后一個。

以查詢第一個目標元素為例，判斷條件就是看mid-1是否等于target，如果不是，那么mid就是我要

找的數了。這依然是二分關鍵。

public class BinarySearch {public static int binarySearch(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else {// 當找到目標值時，判斷是否是第一個出現的位置if (mid == 0 || nums[mid - 1] != target) {//是第一個元素，注意索引越界問題。return mid;} else {right = mid - 1;}
//以下為找最后一個目標元素的判斷條件
//if (mid == nums.length-1 || nums[mid+1]!=target){
//}else{
// left=mid+1;}}}return -1;}public static void main(String[] args) {int[] nums = {1, 3, 8, 8, 8, 9};int target = 8;int result = binarySearch(nums, target);System.out.println("第一個目標值 " + target + " 的索引是: " + result);}
}