序言

心若有陽光，你便會(huì)看見這個(gè)世界有那么多美好值得期待和向往。

決定開一個(gè)算法專欄，希望能幫助大家很好的了解算法。主要深入解析每個(gè)算法，從概念到示例。

我們一起努力，成為更好的自己！

今天第8講，講一下查找算法的二分查找

1 基礎(chǔ)介紹

查找算法是很常見的一類問題，主要是將一組數(shù)據(jù)按照某種規(guī)則進(jìn)行排序。

以下是一些常見的查找算法及其應(yīng)用場景：

1. 布隆過濾器（Bloom Filter）：適用于判斷一個(gè)元素是否存在于一個(gè)大規(guī)模的數(shù)據(jù)集中，時(shí)間復(fù)雜度為O(1)，但有一定的誤判率。
2. 二分查找（Binary Search）：適用于有序數(shù)組中查找元素，時(shí)間復(fù)雜度為O(log n)；
3. 哈希表查找（Hash Table）：適用于快速查找和插入元素，時(shí)間復(fù)雜度為O(1)，但需要額外的存儲(chǔ)空間；
4. 線性查找（Linear Search）：適用于無序數(shù)組中查找元素，時(shí)間復(fù)雜度為O(n)；
5. 插值查找（Interpolation Search）：適用于有序數(shù)組中查找元素，時(shí)間復(fù)雜度為O(log log n)，但是對(duì)于分布不均勻的數(shù)據(jù)集效果不佳；
6. 斐波那契查找（Fibonacci Search）：適用于有序數(shù)組中查找元素，時(shí)間復(fù)雜度為O(log n)，但需要額外的存儲(chǔ)空間；
7. 樹表查找（Tree Search）：適用于快速查找和插入元素，時(shí)間復(fù)雜度為O(log n)，但需要額外的存儲(chǔ)空間；
8. B樹查找（B-Tree）：適用于大規(guī)模數(shù)據(jù)存儲(chǔ)和查找，時(shí)間復(fù)雜度為O(log n)，但需要額外的存儲(chǔ)空間；

一、二分查找介紹

1.1 原理介紹

二分查找算法（Binary Search）是一種用于在有序數(shù)據(jù)集合中查找目標(biāo)元素的高效搜索算法。

它的實(shí)現(xiàn)原理基于分而治之（Divide and Conquer）的思想，通過將查找范圍逐漸縮小一半來快速定位目標(biāo)元素。

下面詳細(xì)講解二分查找算法的實(shí)現(xiàn)原理：

前提條件：

• 數(shù)據(jù)集合必須是有序的，通常是升序排列的。
• 數(shù)據(jù)集合應(yīng)為靜態(tài)，不應(yīng)頻繁插入或刪除元素。

步驟：

1. 初始化指針：首先，確定查找范圍，通常是整個(gè)數(shù)據(jù)集合。然后，初始化兩個(gè)指針：

   • 左指針（left）指向查找范圍的起始位置，通常是0。
   • 右指針（right）指向查找范圍的結(jié)束位置，通常是數(shù)據(jù)集合的最后一個(gè)元素的索引。

2. 查找中間元素：計(jì)算左右指針的中間位置，即 (left + right) / 2。

3. 比較中間元素：將目標(biāo)元素與中間位置的元素進(jìn)行比較。

   • 如果目標(biāo)元素等于中間位置的元素，則找到了目標(biāo)元素，查找結(jié)束。
   • 如果目標(biāo)元素小于中間位置的元素，則更新右指針為中間位置的前一個(gè)位置，將查找范圍縮小為左半部分。
   • 如果目標(biāo)元素大于中間位置的元素，則更新左指針為中間位置的后一個(gè)位置，將查找范圍縮小為右半部分。

4. 重復(fù)步驟2和步驟3：不斷重復(fù)計(jì)算中間位置和比較中間元素，直到以下任一條件滿足：

   • 找到目標(biāo)元素，即目標(biāo)元素等于中間位置的元素。
   • 左指針大于右指針，表示查找范圍為空，目標(biāo)元素不存在。

示例： 假設(shè)有一個(gè)有序數(shù)組 arr，要查找目標(biāo)元素 target。

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17] target = 9

初始時(shí)，left 指向0，right 指向8，中間元素為 arr[4]，即9。

1. 目標(biāo)元素與中間元素相等，查找結(jié)束，找到了目標(biāo)元素。

二分查找算法的關(guān)鍵在于每一次迭代都將查找范圍縮小一半，這導(dǎo)致算法的時(shí)間復(fù)雜度為 O(log n)，其中 n 是數(shù)據(jù)集合的大小。這使得二分查找非常高效，特別適用于大規(guī)模的有序數(shù)據(jù)集合。但需要注意的是，由于它要求數(shù)據(jù)集合必須是有序的，因此如果數(shù)據(jù)無序，需要先進(jìn)行排序操作。

1.2 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

1. 高效性：二分查找的時(shí)間復(fù)雜度為 O(log n)，其中 n 是數(shù)組的長度。由于每次迭代都將搜索范圍減半，因此算法的時(shí)間復(fù)雜度相對(duì)較低。在大型有序數(shù)組中，二分查找比線性查找要快得多。
2. 簡單易實(shí)現(xiàn)：二分查找的實(shí)現(xiàn)相對(duì)簡單，只需按照一定的步驟進(jìn)行比較和調(diào)整指針即可。

缺點(diǎn)：

1. 僅適用于有序數(shù)組：二分查找要求數(shù)組必須是有序的，否則無法保證正確的查找結(jié)果。如果數(shù)組未排序，需要先進(jìn)行排序操作，這可能會(huì)增加額外的時(shí)間復(fù)雜度。
2. 內(nèi)存占用較大：二分查找通常需要占用較大的內(nèi)存空間，因?yàn)樗枰鎯?chǔ)整個(gè)數(shù)組。在某些情況下，這可能會(huì)成為一個(gè)問題，特別是當(dāng)處理大型數(shù)組時(shí)。
3. 難以處理插入和刪除操作：二分查找適用于靜態(tài)數(shù)組，即不經(jīng)常進(jìn)行插入和刪除操作的數(shù)組。如果需要頻繁地插入或刪除元素，由于需要保持?jǐn)?shù)組有序性，可能需要進(jìn)行額外的操作，導(dǎo)致效率降低。

所以，二分查找算法在查找有序數(shù)組中的元素時(shí)非常高效。它的主要優(yōu)點(diǎn)是高效性和簡單易實(shí)現(xiàn)。

然而，它的缺點(diǎn)是僅適用于有序數(shù)組、內(nèi)存占用較大以及難以處理插入和刪除操作。

因此，在選擇使用二分查找時(shí)，需要根據(jù)具體的問題和數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)綜合考慮其優(yōu)缺點(diǎn)。

1.3 復(fù)雜度

這種算法的效率很高，時(shí)間復(fù)雜度為O(log n)，適用于大規(guī)模數(shù)據(jù)集合。

1.4?使用場景

二分查找適用于以下場景：

1. 有序數(shù)組：二分查找要求數(shù)組是有序的，因此當(dāng)我們需要在一個(gè)已排序的數(shù)組中查找某個(gè)元素時(shí)，可以使用二分查找來提高查找效率。

2. 查找靜態(tài)數(shù)據(jù)：如果數(shù)據(jù)集合是靜態(tài)的，即不會(huì)頻繁地插入、刪除或修改元素，而是在固定的數(shù)據(jù)集上進(jìn)行查找操作，那么二分查找是一個(gè)很好的選擇。

3. 大型數(shù)據(jù)集合：二分查找的時(shí)間復(fù)雜度為 O(log n)，其中 n 是數(shù)組的長度。相比線性查找的 O(n) 時(shí)間復(fù)雜度，二分查找在大型數(shù)據(jù)集合中的查找效率更高。

4. 查找邊界值：由于二分查找可以快速定位有序數(shù)組中的中間元素，因此它在查找邊界值或者某個(gè)特定范圍內(nèi)的元素時(shí)非常有用。例如，在一個(gè)有序整數(shù)數(shù)組中查找某個(gè)元素第一次出現(xiàn)的位置或最后一次出現(xiàn)的位置。

5. 數(shù)值區(qū)間判斷：對(duì)于滿足某種數(shù)值規(guī)律的數(shù)組，可以使用二分查找進(jìn)行區(qū)間判斷。例如，對(duì)于一個(gè)有序的數(shù)值范圍數(shù)組，可以使用二分查找確定某個(gè)數(shù)值是否在某個(gè)區(qū)間內(nèi)。

二、代碼實(shí)現(xiàn)

2.1 Python實(shí)現(xiàn)

代碼示例

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # 如果未找到目標(biāo)元素，返回 -1

# 示例使用
arr = [1, 3, 5, 7, 9, 11, 13]
target = 7

result = binary_search(arr, target)

if result != -1:
    print("目標(biāo)元素在數(shù)組中的索引為:", result)
else:
    print("目標(biāo)元素不在數(shù)組中")

代碼講解

在這個(gè)示例中，我們定義了一個(gè)名為?binary_search?的函數(shù)，它接受一個(gè)有序數(shù)組?arr?和目標(biāo)元素?target?作為輸入?yún)?shù)。算法使用兩個(gè)指針?left?和?right?來表示搜索的區(qū)間。開始時(shí)，left?指向數(shù)組的起始位置，right?指向數(shù)組的末尾位置。

然后，算法進(jìn)入一個(gè)循環(huán)，當(dāng)?left?小于等于?right?時(shí)，持續(xù)執(zhí)行以下步驟：計(jì)算中間元素的索引?mid，并將其與目標(biāo)元素進(jìn)行比較。如果?arr[mid]?等于?target，則找到了目標(biāo)元素，返回?mid。如果?arr[mid]?小于?target，則說明目標(biāo)元素可能在?mid?的右側(cè)，將?left?更新為?mid + 1。

1. 如果?arr[mid]?大于?target，則說明目標(biāo)元素可能在?mid?的左側(cè)，將?right?更新為?mid - 1。
2. 如果循環(huán)結(jié)束時(shí)仍未找到目標(biāo)元素，說明目標(biāo)元素不存在于數(shù)組中，返回 -1。

運(yùn)行結(jié)果

運(yùn)行上述代碼的結(jié)果將會(huì)是：

目標(biāo)元素在數(shù)組中的索引為: 3

根據(jù)給定的有序數(shù)組?[1, 3, 5, 7, 9, 11, 13]?和目標(biāo)元素?7，經(jīng)過二分查找算法，找到了目標(biāo)元素在數(shù)組中的索引位置為 3。

2.2 Java實(shí)現(xiàn)

代碼示例

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;  // 如果未找到目標(biāo)元素，返回 -1
    }

    // 示例使用
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;

        int result = binarySearch(arr, target);

        if (result != -1) {
            System.out.println("目標(biāo)元素在數(shù)組中的索引為: " + result);
        } else {
            System.out.println("目標(biāo)元素不在數(shù)組中");
        }
    }
}

代碼講解

在這個(gè)示例中，定義了一個(gè)名為?BinarySearch?的類，其中包含了一個(gè)靜態(tài)方法?binarySearch。該方法接受一個(gè)有序數(shù)組?arr?和目標(biāo)元素?target?作為輸入?yún)?shù)，并返回目標(biāo)元素在數(shù)組中的索引。

在?binarySearch?方法中，使用兩個(gè)指針?left?和?right?來表示搜索的區(qū)間。開始時(shí)，left?指向數(shù)組的起始位置，right?指向數(shù)組的末尾位置。

然后，算法進(jìn)入一個(gè)循環(huán)，當(dāng)?left?小于等于?right?時(shí)，持續(xù)執(zhí)行以下步驟：

1. 計(jì)算中間元素的索引?mid，并將其與目標(biāo)元素進(jìn)行比較。
2. 如果?arr[mid]?等于?target，則找到了目標(biāo)元素，返回?mid。
3. 如果?arr[mid]?小于?target，則說明目標(biāo)元素可能在?mid?的右側(cè)，將?left?更新為?mid + 1。
4. 如果?arr[mid]?大于?target，則說明目標(biāo)元素可能在?mid?的左側(cè)，將?right?更新為?mid - 1。
5. 如果循環(huán)結(jié)束時(shí)仍未找到目標(biāo)元素，說明目標(biāo)元素不存在于數(shù)組中，返回 -1。

運(yùn)行結(jié)果

運(yùn)行上述 Java 代碼的結(jié)果將會(huì)是：

目標(biāo)元素在數(shù)組中的索引為: 3

根據(jù)給定的有序數(shù)組?[1, 3, 5, 7, 9, 11, 13]?和目標(biāo)元素?7，經(jīng)過二分查找算法，找到了目標(biāo)元素在數(shù)組中的索引位置為 3。

三、圖書推薦

清華社【秋日閱讀企劃】領(lǐng)券立享優(yōu)惠

IT好書 5折疊加10元 無門檻優(yōu)惠券：活動(dòng)

活動(dòng)時(shí)間：9月4日-9月17日，先到先得，快快搶

圖書名稱：

• 《Python從入門到精通（第3版）（軟件開發(fā)視頻大講堂）》

圖書介紹

《Python從入門到精通（第3版）》從初學(xué)者角度出發(fā)，通過通俗易懂的語言、豐富多彩的實(shí)例，詳細(xì)介紹了使用Python進(jìn)行程序開發(fā)應(yīng)該掌握的各方面技術(shù)。

全書共分27章，包括初識(shí)Python、Python語言基礎(chǔ)、運(yùn)算符與表達(dá)式、流程控制語句、列表和元組、字典和集合、字符串、Python中使用正則表達(dá)式、函數(shù)、面向?qū)ο蟪绦蛟O(shè)計(jì)、模塊、文件及目錄操作、操作數(shù)據(jù)庫、使用進(jìn)程和線程、網(wǎng)絡(luò)編程、異常處理及程序調(diào)試、Pygame游戲編程、推箱子游戲、網(wǎng)絡(luò)爬蟲開發(fā)、火車票分析助手、數(shù)據(jù)可視化、京東電商銷售數(shù)據(jù)分析與預(yù)測、Web編程、Flask框架、e起去旅行網(wǎng)站、Python自動(dòng)化辦公、AI圖像識(shí)別工具等內(nèi)容。

書中所有知識(shí)都結(jié)合具體實(shí)例進(jìn)行介紹，涉及的程序代碼都給出了詳細(xì)的注釋，讀者可輕松領(lǐng)會(huì)Python程序開發(fā)的精髓，快速提升開發(fā)技能。?

?

參與方式?

圖書數(shù)量：本次送出 3 本 ? ?。?！??????
活動(dòng)時(shí)間：截止到 2023-09-16?12:00:00

抽獎(jiǎng)方式：

• 評(píng)論區(qū)隨機(jī)抽取小伙伴！

留言內(nèi)容，以下方式都可以：

• 根據(jù)文章內(nèi)容進(jìn)行高質(zhì)量評(píng)論

參與方式：關(guān)注博主、點(diǎn)贊、收藏，評(píng)論區(qū)留言?

中獎(jiǎng)名單?

???? 獲獎(jiǎng)名單????

?中獎(jiǎng)名單：請(qǐng)關(guān)注博主動(dòng)態(tài)

名單公布時(shí)間：2023-09-16?下午文章來源地址http://www.zghlxwxcb.cn/news/detail-728244.html

到了這里，關(guān)于【算法系列 | 8】深入解析查找算法之—二分查找的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！