二分查找筆記(1)

二分查找

• 什麼是二分查找？
• 二分查找 demo
• 左右邊界查找
• • 調試
• 總結

什麼是二分查找？

對一個有序（局部有序也可）的序列，每次搜尋都通過條件判斷 target 可能在的搜尋區間，排除另一半不可能存在 target 的搜尋區間。時間複雜度往往是 O(logn)

二分查找 demo

該模闆适用于：查找可以通過通路數組中的單個索引來确定的元素或條件

給定一個 n 個元素有序的（升序）整型數組 nums 和一個目标值 target ，寫一個函數搜尋 nums 中的 target，如果目标值存在傳回下标，否則傳回 -1。

public int search(int[] nums, int target) {
    if(nums.length == 0){
        return -1;
    }
    int left,mid,right;
    left = 0;
    right = nums.length - 1; // 不要忘了右索引的下标是數組長度 -1 ；
    while(left<=right){
    	// 無符号右移  等價于 left + (right-left) / 2 編譯器一般會自動轉為位運算
        mid = (left+right) >>> 1;
        if(nums[mid] == target){
            return mid;
        }else if(nums[mid] > target){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return -1;
}
           

缺點是遇到重複的target，不能找到最左或最右的那個。

下面是關于左右邊界查找的demo。

左右邊界查找

使用一個ans 變量儲存最新的 mid 邊界下标用來傳回，不斷向左或右減少搜尋區間。

// low =true 左搜尋，false 右搜尋
public int binarysearch(int[] nums,int target,boolean low){
     int left,right,mid,ans;
     ans = -1;
     left = 0;
     right = nums.length - 1;
     while(left <= right){ // 當 left > right 結束，即 left = right + 1
         mid = left + (right-left) / 2;
         if(nums[mid] == target){
             if(low){
                 right = mid - 1;
             }else{
                 left = mid + 1;
             }
             ans = mid;
         }else if(nums[mid] > target){
             right = mid - 1;
         }else if(nums[mid] < target){
             left = mid + 1;
         }
     }
     return ans;
 }
           

調試

public class Main {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4};
        Binarysearch binarysearch = new Binarysearch();
        int index = binarysearch.binarysearch(nums, 2);
        System.out.println("2 在 {1, 2, 3, 4} 的索引是：" + index);

        int[] nums2 = new int[]{1, 2, 2, 2, 4};
        int[] nums3 = new int[]{2,2};

        int res = binarysearch.binarysearch(nums2, 2, true);
        System.out.println("2 在 {1, 2, 2, 2, 4} 的左邊界索引是：" + res);
        res = binarysearch.binarysearch(nums2, 2, false);
        System.out.println("2 在 {1, 2, 2, 2, 4} 的右邊界索引是：" + res);

        res = binarysearch.binarysearch(nums3, 2, true);
        System.out.println("2 在 {2,2} 的左邊界索引是：" + res);

        res = binarysearch.binarysearch(nums3, 2, false);
        System.out.println("2 在 {2,2} 的右邊界索引是：" + res);
    }
}
           

2 在 {1, 2, 3, 4} 的索引是：1
2 在 {1, 2, 2, 2, 4} 的左邊界索引是：1
2 在 {1, 2, 2, 2, 4} 的右邊界索引是：3
2 在 {2,2} 的左邊界索引是：0
2 在 {2,2} 的右邊界索引是：1

Process finished with exit code 0
           

總結

二分查找的整體思路關鍵在于每次搜尋要減少一半區間的條件，遇到判斷有序數組是否存在某元素時還比較簡單，遇到需要查找左右邊界的就比較麻煩，需要考慮許多細節，避免死循環，考慮傳回值。。。