快捷導(dǎo)航

Java實現(xiàn)二分法變種的示例代碼

更新時間：2024年04月30日 10:14:05 作者：一葉浮萍?xì)w大海

這篇文章主要為大家介紹了Java實現(xiàn)二分法變種的示例代碼復(fù),有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

一、引言

二分法，又稱二分查找、折半查找，是一種在有序數(shù)組中查找某一特定元素的搜索算法。其核心思想是通過將目標(biāo)數(shù)據(jù)與有序的數(shù)據(jù)序列進(jìn)行比較，每次查找都將數(shù)據(jù)序列一分為二，確定目標(biāo)數(shù)據(jù)在哪一半中，直到找到目標(biāo)數(shù)據(jù)或者確定目標(biāo)數(shù)據(jù)不存在。二分法的時間復(fù)雜度為O(log n)，相比于順序查找的O(n)，效率更高。然而，在實際應(yīng)用中，我們可能會遇到一些特殊情況，需要對二分法進(jìn)行一定的變種以滿足特定的需求。本文將介紹幾種常見的二分法變種，并給出Java實現(xiàn)。

二、二分法變種

查找第一個等于給定值的元素

在某些情況下，我們不僅需要判斷數(shù)組中是否存在某個元素，還需要找到該元素在數(shù)組中的第一個位置。這可以通過在二分查找的基礎(chǔ)上稍作修改來實現(xiàn)。當(dāng)找到目標(biāo)元素時，我們并不立即返回，而是繼續(xù)向左查找，直到找到第一個等于目標(biāo)值的元素。

Java實現(xiàn)如下：

public int findFirstEqual(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid - 1; // 繼續(xù)向左查找
        } else {
            left = mid + 1;
        }
    }
    // 檢查left是否越界以及nums[left]是否等于target
    if (left >= 0 && nums[left] == target) {
        return left;
    } else {
        return -1; // 未找到
    }
}

查找最后一個等于給定值的元素

與查找第一個等于給定值的元素類似，我們也可以通過修改二分查找算法來找到最后一個等于給定值的元素。當(dāng)找到目標(biāo)元素時，我們并不立即返回，而是繼續(xù)向右查找，直到找到最后一個等于目標(biāo)值的元素。

Java實現(xiàn)如下：

public int findLastEqual(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1; // 繼續(xù)向右查找
        }
    }
    // 檢查right是否越界以及nums[right]是否等于target
    if (right >= 0 && nums[right] == target) {
        return right;
    } else {
        return -1; // 未找到
    }
}

查找插入位置

在某些情況下，我們需要在有序數(shù)組中插入一個元素，并返回插入后的索引。如果數(shù)組中已存在該元素，則返回該元素的索引；否則，返回應(yīng)該插入的位置。這同樣可以通過修改二分查找算法來實現(xiàn)。

Java實現(xiàn)如下：

public int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid; // 找到目標(biāo)元素，返回其索引
        } else if (nums[mid] < target) {
            left = mid + 1; // 目標(biāo)元素在右半部分
        } else {
            right = mid - 1; // 目標(biāo)元素在左半部分或不存在（此時right指向的位置應(yīng)插入target）
        }
    }
    // 未找到目標(biāo)元素，返回應(yīng)插入的位置
    return left;
}

三、總結(jié)

本文介紹了三種常見的二分法變種：查找第一個等于給定值的元素、查找最后一個等于給定值的元素和查找插入位置，并給出了相應(yīng)的Java實現(xiàn)。這些變種算法都是在原始二分查找算法的基礎(chǔ)上進(jìn)行了一定的修改和擴(kuò)展，以滿足特定的需求。在實際應(yīng)用中，我們可以根據(jù)具體的問題選擇合適的變種算法來解決問題。

到此這篇關(guān)于Java實現(xiàn)二分法變種的示例代碼的文章就介紹到這了,更多相關(guān)Java 二分法變種內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: