快捷導(dǎo)航

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

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

這篇文章主要為大家介紹了Java實(shí)現(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ù)不存在。二分法的時(shí)間復(fù)雜度為O(log n)，相比于順序查找的O(n)，效率更高。然而，在實(shí)際應(yīng)用中，我們可能會遇到一些特殊情況，需要對二分法進(jìn)行一定的變種以滿足特定的需求。本文將介紹幾種常見的二分法變種，并給出Java實(shí)現(xiàn)。

二、二分法變種

查找第一個(gè)等于給定值的元素

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

Java實(shí)現(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; // 未找到
    }
}

查找最后一個(gè)等于給定值的元素

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

Java實(shí)現(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ù)組中插入一個(gè)元素，并返回插入后的索引。如果數(shù)組中已存在該元素，則返回該元素的索引；否則，返回應(yīng)該插入的位置。這同樣可以通過修改二分查找算法來實(shí)現(xiàn)。

Java實(shí)現(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)元素在左半部分或不存在（此時(shí)right指向的位置應(yīng)插入target）
        }
    }
    // 未找到目標(biāo)元素，返回應(yīng)插入的位置
    return left;
}

三、總結(jié)

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

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

您可能感興趣的文章: