欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

一篇文章帶你了解C語言二分查找

 更新時間:2021年08月25日 10:45:54   作者:ZDDWLIG  
這篇文章主要為大家詳細介紹了C語言二分查找法,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下

我們常常需要對數(shù)據(jù)進行查找,修改,查找數(shù)據(jù)有許多方法,我們先看看最簡單的順序查找

int main()
{
	int i, k = 0;
	scanf("%d", &k);
	int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	for (i = 0; i < sz; i++)
	{
		if (arr[i] == k)
		{
			printf("找到了,它是%d", arr[i]);
		}
	}
	return 0;
}

順序查找絕大多數(shù)情況有效但是由于它是一個一個元素進行查找,其效率很低,只有一個for循環(huán)所有其時間復(fù)雜度為O(n)。我們希望有一個更高效的查找方法,接下來便是二分查找,先來看看一個順序查找和二分查找的直觀比較。

從上面的圖中我們感受到二分查找的關(guān)鍵:找到最左邊元素(low)和最右邊元素(high),確定中間元素(mid),比較中間元素(mid)和目標元素(k)的大小,調(diào)整low和high,再確定新的mid....我們要不斷確定mid直到找到k,自然需要用到循環(huán),我們有明確的目標:找到k。因此選擇while循環(huán),找到k后循環(huán)不再進行,而當low和high之間還有元素,即low在high的左邊或與之重合,k就依然可能存在,所以循環(huán)條件為low<=high,接下來的問題在于怎樣調(diào)整low和high的值,mid和k比較無非就三種情況:mid<k,mid>k,mid=k。第一種情況,k在mid的右邊,我們將low調(diào)整為mid+1,high不用調(diào)整;第二種情況,k在mid的左邊,我們將high調(diào)整為mid-1,low不用調(diào)整。最后一種情況最簡單,我們已經(jīng)找到了k,直接將mid打印出來就行了,代碼如下:

#include <stdio.h>
int main()
{
	int k = 0;
	scanf("%d", &k);
	int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int sz = sizeof(arr) / sizeof (arr[0]);
	int low = 0;
	int high = sz-1;
	while (low <= high)
	{
		int mid = (low + high) / 2;
		if (arr[mid] > k)
		{
			high = mid - 1;
		}
		else if (arr[mid] < k)
		{
			low = mid + 1;
		}
		else
		{
			printf("找到了,它是:%d", arr[a]);
			break;
		}
	}
	if (l>r)
		printf("沒找到,請重新輸入");
	return 0;
}

二分查找的時間復(fù)雜度的問題:總共有n個元素,每次查找的區(qū)間大小就是n,n/2,n/4,…,n/2^k(接下來操作元素的剩余個數(shù)),其中k就是循環(huán)的次數(shù)。由于n/2^k取整后>=1,即令n/2^k=1,可得k=log2n,(是以2為底,n的對數(shù)),所以時間復(fù)雜度可以表示O(logn),確實比順序查找快不少,但是二分查找有一個較大的局限性:只能查找有序數(shù)組的元素,即組數(shù)字必須是升序或降序。

總結(jié)

本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

相關(guān)文章

  • C++ OpenCV繪制簡易直方圖DrawHistImg

    C++ OpenCV繪制簡易直方圖DrawHistImg

    本文主要介紹了一個能繪制簡易直方圖的簡單函數(shù)DrawHistImg,可以幫助大家快速掌握繪制的原理,可以根據(jù)自己的創(chuàng)意對其進行改善和補充。需要的朋友可以參考一下
    2021-12-12
  • C語言?超詳細總結(jié)講解二叉樹的概念與使用

    C語言?超詳細總結(jié)講解二叉樹的概念與使用

    二叉樹可以簡單理解為對于一個節(jié)點來說,最多擁有一個上級節(jié)點,同時最多具備左右兩個下級節(jié)點的數(shù)據(jù)結(jié)構(gòu)。本文將詳細介紹一下C++中二叉樹的概念和結(jié)構(gòu),需要的可以參考一下
    2022-04-04
  • 非常漂亮的新年祝福!C語言實現(xiàn)漂亮的煙花效果

    非常漂亮的新年祝福!C語言實現(xiàn)漂亮的煙花效果

    非常漂亮的新年祝福!這篇文章主要介紹了C語言實現(xiàn)漂亮的煙花效果,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-02-02
  • Windows下ncnn環(huán)境配置教程詳解(VS2019)

    Windows下ncnn環(huán)境配置教程詳解(VS2019)

    這篇文章主要介紹了Windows下ncnn環(huán)境配置(VS2019),本文通過圖文并茂的形式給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-03-03
  • C語言的多級指針你了解嗎

    C語言的多級指針你了解嗎

    這篇文章主要介紹了C語言中的多級指針,本文給大家介紹的非常詳細,具有參考借鑒價值,需要的朋友可以參考下,希望能給你帶來幫助
    2021-08-08
  • C++可調(diào)用對象callable object深入分析

    C++可調(diào)用對象callable object深入分析

    所謂的callable object,表示可以被某種方式調(diào)用其某些函數(shù)的對象。它可以是:一個函數(shù)、一個指向成員函數(shù)的指針、一個函數(shù)對象,該對象擁有operator()、一個lambda表達式,嚴格的說它是一種函數(shù)對象
    2022-08-08
  • windows下vscode使用cmake的方法

    windows下vscode使用cmake的方法

    這篇文章主要介紹了windows下vscode使用cmake的方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2021-03-03
  • C++?測試框架GoogleTest入門介紹

    C++?測試框架GoogleTest入門介紹

    這篇文章主要為大家介紹了C++測試框架GoogleTest入門基礎(chǔ),有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-04-04
  • C++中的內(nèi)存對齊實例詳解

    C++中的內(nèi)存對齊實例詳解

    這篇文章主要介紹了C++中的內(nèi)存對齊實例詳解的相關(guān)資料,這里不僅提供實現(xiàn)方法及代碼還提供了手工制作圖,來幫助到大家理解這部分知識,需要的朋友可以參考下
    2017-07-07
  • C++依賴倒轉(zhuǎn)原則和里氏代換原則有什么好處

    C++依賴倒轉(zhuǎn)原則和里氏代換原則有什么好處

    設(shè)計模式(Design pattern)代表了最佳的實踐,通常被有經(jīng)驗的面向?qū)ο蟮能浖_發(fā)人員所采用。設(shè)計模式是軟件開發(fā)人員在軟件開發(fā)過程中面臨的一般問題的解決方案。本篇介紹設(shè)計模式七大原則之一的依賴倒轉(zhuǎn)原則
    2023-02-02

最新評論