目錄

二分查找

思路

總體

細節

問題一，為什么循環的條件是left<=right? ?,為什么要有等號呢

問題二，為什么中間值是left +(right - left) / 2

問題三，為什么最后返回的是左邊的值呢

情況 1：target?存在于數組中

情況 2：target?不存在于數組中

例題1

代碼實現

Java

Python?

例題2

Java

Python

例題三

Java

Python

總結

---

二分查找

思路

總體

二分查找前提是已經是從小到大排序了，就是對半著查找

一開始先看最中間那個

如果等于，那就找到了，直接返回

如果目標小于中間值，那么把右邊界賦值為中間值減一

如果目標大于中間值，那么把左邊界賦值為中間值加一

細節

問題一，為什么循環的條件是left<=right? ?,為什么要有等號呢

• 當?left == right?時，搜索區間仍然包含?一個元素（即?nums[left]?或?nums[right]），需要檢查這個元素是否等于?target。

問題二，為什么中間值是left +(right - left) / 2

(right - left)只是偏移量，在0~5是可以用的，?但是如果最左邊不是0，那就錯了，要加上最左邊

一開始寫的是（left +right）/2? ? 但是這樣有可能會溢出? ，超出java? int類型的最大值，導致結果是負數，? java? int最大值是2,147,483,647（231 - 1）? ? ?，java的第一位是符號位，如果你超出了最大值，就會變成負數，負數除2還是負數。

int max = Integer.MAX_VALUE; // 2147483647 (0x7FFFFFFF)
int overflow = max + 1;      // 溢出后變為 -2147483648 (0x80000000)

注意：

>>是有符號右移 / 算術右移? ? ?，移了之后原符號不變

>>>（無符號右移 / 邏輯右移），?，移了之后原符號可能改變

可以采用

方法一：left +(right - left) / 2

方法二：（left +right）>>>1,是向下取整的

雖然說超出了是負數，但其實二進制的數還是一樣的，只是java把第一位看作是符號位，所以你向右移一位，其實就是除二向下取整

問題三，為什么最后返回的是左邊的值呢

情況 1：target?存在于數組中

• 在循環中直接返回?mid，不會走到最后的?return?語句。

情況 2：target?不存在于數組中

• left?的物理意義：

  • 它是?target?應該插入的位置，即第一個比?target?大的元素的位置。

  • 如果所有元素都比?target?小，left?會停在?len(nums)（數組末尾之后）。

  • 如果所有元素都比?target?大，left?會停在?0（數組開頭）。

• right?的問題：

  • right?指向的是最后一個比?target?小的元素，插入后會破壞順序。

  • 例如?nums = [1,3,5,6]，target = 2：

    • 終止時?left = 1,?right = 0。

    • 插入到?left（1）是正確的?[1, **2**, 3, 5, 6]，而?right（0）會錯誤地插入到開頭。

例題1

代碼實現

Java

package Test;import java.util.HashMap;
import java.util.Map;class Solution {public static int searchInsert(int[] nums, int target) {int length = nums.length;int left = 0;int right = length - 1;while (left <= right) {int mid = left +(right - left) / 2;//為什么是這樣呢，(right - left)只是偏移量，在0~5是可以用的// 但是如果最左邊不是0，那就錯了，要加上最左邊if (nums[mid] == target) {return mid;}else if(target<nums[mid]){right = mid - 1;}else if (target>nums[mid]) {left = mid + 1;}}return left;}public  static void main(String[] args) {int[] nums = {1,3,5,6};System.out.println(searchInsert(nums, 2));for (int num : nums) {System.out.print(num);}}
}

Python?

注意python中，/是有小數點的除? ?// 是整除，向下取整

class Solution:def searchInsert( self,nums, target):length = len(nums)left = 0right = length - 1while left<=right:mid=left+(right-left)//2if target==nums[mid]:return midif target<nums[mid]:right=mid-1if target>nums[mid]:left=mid+1return left;
solution = Solution()
nums=[1,3,5,6]
print(solution.searchInsert(nums, 2))  # 輸出: 1

例題2

Java

class Solution {public int search(int[] nums, int target) {int length = nums.length;int left = 0;int right = length - 1;while (left <= right) {int mid = left +(right - left) / 2;//為什么是這樣呢，(right - left)只是偏移量，在0~5是可以用的// 但是如果最左邊不是0，那就錯了，要加上最左邊if (nums[mid] == target) {return mid;}else if(target<nums[mid]){right = mid - 1;}else if (target>nums[mid]) {left = mid + 1;}}return -1;}
}

Python

class Solution(object):def search(self, nums, target):mid=-1left=0right=len(nums)-1while left<=right:mid=left+(right-left)//2if(nums[mid]==target):return midelif(target<nums[mid]):right=mid-1else:left=mid+1return -1

例題三

Java

在這次寫法中，使用二分法之前，我先判斷了數組是不是為空，和目標值在不在范圍里面，可以避免無效的搜索，是一個優化的方法

package Test;import java.util.HashMap;
import java.util.Map;class Solution {public static int[] searchInsert(int[] nums, int target) {int length = nums.length;int left = 0;int right = length - 1;int leftcadidate=-1;int rightcadidate=-1;int[]result={leftcadidate,rightcadidate};//情況1，數組為空if(length==0)return result;//情況2，目標值超出范圍// 我們知道了這個數組是遞增的，那么我們先取邊界值和目標值比較，如果不再范圍內直接就返回了if(target<nums[0]||target>nums[length-1])return result;//情況三：目標值在范圍里面while (left <= right) {int mid = left +(right - left) / 2;if (nums[mid] == target) {leftcadidate = mid;right = mid - 1;}else if(target<nums[mid]){right = mid - 1;}else if (target>nums[mid]) {left = mid + 1;}}left = 0;right = length - 1;while (left <= right) {int mid = left +(right - left) / 2;if (nums[mid] == target) {rightcadidate=mid;left = mid + 1;}else if(target<nums[mid]){right = mid - 1;}else if (target>nums[mid]) {left = mid + 1;}}result[0]=leftcadidate;result[1]=rightcadidate;return result;}public  static void main(String[] args) {int[] nums = {5,7,7,8,8,10};int target = 6;int [] result=searchInsert(nums, target);for (int i = 0; i < result.length; i++) {System.out.println(result[i]);}}
}

Python

class Solution(object):def searchRange(self, nums, target):mid=-1left=0right=len(nums)-1leftcandidate=-1while left<=right:mid=left+(right-left)//2if(target<nums[mid]):right=mid-1elif(nums[mid]<target):left=mid+1else:right=mid-1leftcandidate=midmid = -1left = 0right = len(nums)-1rightcandidate = -1while left <= right:mid = left + (right - left) // 2if (target < nums[mid]):right = mid - 1elif (nums[mid] < target):left = mid + 1else:left=mid+1rightcandidate = midreturn [leftcandidate,rightcandidate]

總結

1.數組的長度是length，但是數組是從零開始，使用數組的最后一個數字下標是length-1

2.可以先判斷邊界值和數組是否為空來優化算法

3.java創建數組是? ? int nums[]={1,2,3,4,5};

python是? ?nums=[1,2,3,4,5]

4.數組有可能為空，調用nums.length 會拋出異常，所以最開始要先判斷是否為空（為空和數組長度為0是不一樣的）（我的代碼沒有加入這個）。

在python，可以使用

if nums is None:return [-1,-1]

來判斷是否為空