系列文章目錄

?第一章?初階算法（1）：通過簡單的排序算法來認(rèn)識時間復(fù)雜度

?第二章?初階算法（2）：進行詳細(xì)地介紹插入排序的細(xì)節(jié)和時間復(fù)雜度

?第三章 初階算法（3）：二分法的講解與實現(xiàn)，以及二分不止光在有序數(shù)組中的應(yīng)用

目錄

系列文章目錄

前言

一、二分法的講解與實現(xiàn)（C語言）

1.1 為什么在有序數(shù)組中用二分法查找？

1.2 二分查找的講解：

?1.3 二分法的代碼實現(xiàn)：

二、二分法的應(yīng)用（不止在有序數(shù)組中）

2.1 常規(guī)用法

?2.2 非常規(guī)做法（在無需數(shù)組中進行）

總結(jié)

前言

???????哇，轉(zhuǎn)眼就到了第三章，在前兩章內(nèi)（如果想看前兩章的內(nèi)容，請點擊系列文章目錄的鏈接），我們主要講解了時間復(fù)雜度為O(N^2)的排序算法（冒泡排序，選擇排序，插入排序），不知道大家看的如何？

? ? ? ?在這一章，我們主要講述二分法的使用，講述有關(guān)二分法的三道編程題來打破大家對二分法只能用在有序數(shù)組的思想。

一、二分法的講解與實現(xiàn)（C語言）

1.1 為什么在有序數(shù)組中用二分法查找？

???????一般地，我們在一個有序數(shù)組中查找一個數(shù)字，如果我們一一查找是要根據(jù)數(shù)據(jù)量的，有時會很快，有時會很慢！這就比較麻煩，所以我們不能用一一查找。

???????為什么說有時很快，有時很慢呢？假如，我們現(xiàn)在有一個有序數(shù)組（1,2,3,4,5,6,7,8,9,10,11,12,13），如果你要查找1的話， 一一查找只需遍歷一位即可；但如果你要查找13的話，則需要將整個數(shù)組遍歷完。

???????此時，這個要查找的數(shù)組是一個有序數(shù)組，我們就可以利用有序數(shù)組的特性去使用二分查找去尋找我們所要查找的數(shù)字。

1.2 二分查找的講解：

???????在上面的引子中說在一個有序數(shù)組中使用二分查找，那么二分查找是如何實現(xiàn)的呢？

?二分查找的基本思路是：先找到中間的數(shù)與要查找數(shù)進行比較，然后分情況：

? ? ? ?1）如果比要查找數(shù)小，那么就舍棄左邊一半的數(shù)，在右邊一半的數(shù)再找到中間的數(shù)與要查找數(shù)進行比較，重復(fù)此過程；

? ? ? ?2）如果比要查找數(shù)大，那么就舍棄右邊一半的數(shù)，在左邊一半的數(shù)再找到中間的數(shù)與要查找數(shù)進行比較，重復(fù)此過程；

???????最后，直到查找到最后一個數(shù)。

? ? ? ?接下來，進行估算二分查找的時間復(fù)雜度，用最壞的數(shù)據(jù)進行計算，因為一次代碼流程要舍棄一半的數(shù)，所以時間復(fù)雜度為O(logN)。

?1.3 二分法的代碼實現(xiàn)：

???????經(jīng)過上面的詳細(xì)分析后，小編覺得各位看官已經(jīng)充分了解了二分法的思路了，那么接下來，和小編進行二分法的實現(xiàn)吧！

實現(xiàn)二分法的代碼如下：

    int left = 0;
    int right = n - 1;
    while (left <= (right - 1)){     //判斷條件是左邊指向的位置大于右邊指向的位置
        int mid = (left + right) / 2;//中點的位置要隨時更新，以便求出最新的中點坐標(biāo)
        if(k > arr[n - 1])      //如果要查找的數(shù)大于數(shù)組的最后一個數(shù)時，則不需要繼續(xù)查找
            break;
        if (arr[mid] == k){
            right = mid;
            if(arr[mid - 1] < arr[mid])  //與中間數(shù)進行比較
                ans = mid;
        }
        if(arr[mid] > k)     //隨時更新中點坐標(biāo)
            right = mid;  
        if(arr[mid] < k)
            left = mid;
    }

二、二分法的應(yīng)用（不止在有序數(shù)組中）

2.1 常規(guī)用法

???????在上面我們已經(jīng)進行過在一個有序數(shù)組中查找某一個數(shù)，接下來，我們將寫出一個變式：查找某個位置。?

題目：你需要輸入一個n，一個數(shù)k，然后輸入一個長度為n個大小的數(shù)組arr，然后你需要在arr上找滿足>=K的最左位置，并且輸出這個位置，如果不存在這個位置就輸出-1。

??????看到這道題面，小編我的第一個反應(yīng)是將這個有序數(shù)組進行遍歷，?只要找到第一個數(shù)字等于k，則是我們所要查找的位置，那么這種方法就和上面小編寫的第一道體題的思想一樣，就是有時很慢。有時很快。

???????這篇文章中，我們學(xué)習(xí)了二分法，就要利用二分法進行解題?；舅悸肥牵合日业?strong>中間的數(shù)與要查找數(shù)進行比較，然后分情況：

? ? ? ?1）如果比要查找數(shù)小，>=K的最左位置應(yīng)該在右邊，那么就舍棄左邊一半的數(shù)，在右邊一半的數(shù)再找到中間的數(shù)與要查找數(shù)進行比較，重復(fù)此過程；

? ? ? ?2）如果比要查找數(shù)等于或大于，>=K的最左位置應(yīng)該在右邊，那么就舍棄右邊一半的數(shù)，如果等于k的話進行標(biāo)記，在左邊一半的數(shù)再找到中間的數(shù)與要查找數(shù)進行比較，重復(fù)此過程；最后將整個數(shù)組進行遍歷，找到第一個標(biāo)記的數(shù)字。

???????最后，直到查找到最后>=K一個數(shù)。

實現(xiàn)題目的代碼如下：

int main()
{
	int n = 0, k = 0;
	scanf("%d %d", &n, &k);
	int a[1000000];
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	int left = 0;
	int right = n - 1;
	int mid = 0;
	int reslut = -1;    //因為如果找不到，就輸出-1
	while (left <= right){
		mid = (left + right) / 2;
		if (a[mid] >= k){
			reslut = mid;
			right = mid - 1;
		}
		else
			left = mid + 1;
	}
	printf("%d\n", reslut);
	return 0;
}

?2.2 非常規(guī)做法（在無需數(shù)組中進行）

???????二分法真的只能用在有序數(shù)組中嗎？小編在了解完這個題目后，也是大吃一驚！答案是可以的!

???????接下來，跟隨小編的步伐進行學(xué)習(xí)吧！看這道題目：局部最小值問題。

局部最小的概念：1）數(shù)組中0位置的數(shù)比1位置的數(shù)要小；

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2）數(shù)組中N-1位置的數(shù)比N-2位置的數(shù)要小；

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?3）數(shù)組中第i位置的數(shù)要比兩邊位置的數(shù)都要小。

題目： 給定無序數(shù)組arr,已知arr中任意兩個相鄰的數(shù)都不相等，只需要返回arr中任意一個局部最小出現(xiàn)的位置即可，如果不存在這個位置就輸出-1。

???????小編進行分析可得：

???????先判斷0位置的數(shù)和1位置的數(shù)，再判斷N-1位置的數(shù)和N-2位置的數(shù)。如果這兩種情況都不成立，那么一定會出現(xiàn)一開始是下降的，在最后是上揚的，又因為數(shù)組中每兩個數(shù)都不相同，所以在1到N-2中一定有局部最小。

???????接下來，我們就可以利用二分進行舍棄數(shù)字。找到中間位置的數(shù)與兩邊位置的數(shù)進行比較，如果都小于，則返回中間位置的數(shù)；如果有一邊不小于，則舍棄一半，在另一半繼續(xù)尋找。

實現(xiàn)題目的代碼如下：

int main() {
    int n = 0;
    scanf("%d", &n);
    int a[100000];
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    int left = 0;
    int right = n - 1;
    int mid = -1;
    if (n == 1 || a[0] < a[1]) {
        printf("%d\n", 0);
        return 0;
    }
    else if (a[n - 1] < a[n - 2]) {
        printf("%d\n", n - 1);
        return 0;
    } else {
        while (left <= right) {
            mid = (left + right) / 2;

            if (a[mid] > a[mid - 1]) {
                right = mid - 1;
            }
            else if (a[mid] > a[mid + 1]) {
                left = mid + 1;
            } else {
                //flag = 1;
                printf("%d\n", mid);
                return 0;
            }
        }
    }
    return 0;
}

總結(jié)

???????以上就是今天要講的內(nèi)容，本文介紹了二分法及其在無序數(shù)組中的應(yīng)用，過幾天小編會進行編寫關(guān)于二分法的一些習(xí)題，希望大家看完以后，進行點評，謝謝大家！文章來源地址http://www.zghlxwxcb.cn/news/detail-626229.html

到了這里，關(guān)于初階算法（3）：二分法的講解與實現(xiàn)（C語言），以及二分不止光在有序數(shù)組中的應(yīng)用的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！