快捷導(dǎo)航

Java二分查找算法與數(shù)組處理的應(yīng)用實例

更新時間：2022年07月20日 09:34:23 作者：風(fēng)鈴聽雨~

二分查找法，又叫做折半查找法，它是一種效率較高的查找方法。數(shù)組對于每一門編程語言來說都是重要的數(shù)據(jù)結(jié)構(gòu)之一，當(dāng)然不同語言對數(shù)組的實現(xiàn)及處理也不盡相同。Java 語言中提供的數(shù)組是用來存儲固定大小的同類型元素

1.特殊數(shù)組的特征值

題目描述

思路詳解

看到本題，首先思考需要排序，然后查找，這里為了效率采用二分查找。

假設(shè)定義x=（left+riht）/ 2，每次查找到nums中第一個大于等于X的元素下標(biāo)，判斷大于等于X的個數(shù)與X的關(guān)系，進(jìn)行分情況修改左右邊界。

代碼與結(jié)果

class Solution {
    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int left = 0, right = n;
        while (left <= right) {
            int x = (left + right) >> 1;
            int idx = binarySearch(nums, x); // nums中第一個大于等于x的元素位置
            if (x == n - idx) {
                return x;
            } else if (x < n - idx) { // 大于等于x的元素太多了，所以下一輪搜索要增大x的取值范圍
                left = x + 1;
            } else { // 反之，減少x的取值范圍
                right = x - 1;
            }
        }
        return -1;
    }
    private static int binarySearch(int[] nums, int x) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            int val = nums[mid];
            if (val >= x) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

2.在D天內(nèi)送達(dá)包裹的能力

題目描述

思路詳解

假設(shè)當(dāng)船的運(yùn)載能力為 x 時，我們可以在days 天內(nèi)運(yùn)送完所有包裹，那么只要運(yùn)載能力大于 x，我們同樣可以在 days 天內(nèi)運(yùn)送完所有包裹：我們只需要使用運(yùn)載能力為 x時的運(yùn)送方法即可。

由于必須按照數(shù)組weights 中包裹的順序進(jìn)行運(yùn)送，因此我們從數(shù)組 weights 的首元素開始遍歷，將連續(xù)的包裹都安排在同一天進(jìn)行運(yùn)送。當(dāng)這批包裹的重量大于運(yùn)載能力 x 時，我們就需要將最后一個包裹拿出來，安排在新的一天，并繼續(xù)往下遍歷。當(dāng)我們遍歷完整個數(shù)組后，就得到了最少需要運(yùn)送的天數(shù)。

代碼與結(jié)果

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        // 確定二分查找左右邊界
        int left = Arrays.stream(weights).max().getAsInt(), right = Arrays.stream(weights).sum();
        while (left < right) {
            int mid = (left + right) / 2;
            // need 為需要運(yùn)送的天數(shù)
            // cur 為當(dāng)前這一天已經(jīng)運(yùn)送的包裹重量之和
            int need = 1, cur = 0;
            for (int weight : weights) {
                if (cur + weight > mid) {
                    ++need;
                    cur = 0;
                }
                cur += weight;
            }
            if (need <= days) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

3.咒語和藥水的成功對數(shù)

題目描述

思路詳解

本題采用二分查找的方法進(jìn)行解題。

首先我們對藥水的數(shù)組進(jìn)行排序，其次我們遍歷咒術(shù)數(shù)組，利用二分查找的思想在藥水?dāng)?shù)組中查找，與成功值最接近的數(shù)值，存入到答案數(shù)組中。

有個小細(xì)節(jié)，判斷時候1l * power * potions[mid] < success 這樣做是為了把數(shù)字轉(zhuǎn)化為long型，避免錯誤哦。

代碼與結(jié)果

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] ans = new int[spells.length];
        Arrays.sort(potions);
        for (int i = 0; i < spells.length; i++) {
            int power = spells[i];
            int left = 0;
            int right = potions.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (1l * power * potions[mid] < success) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            ans[i] = potions.length - left;
        }
        return ans;
    }
}