您好,登錄后才能下訂單哦!
今天又get到了好多新知識,和大家share一下吧。
折半查找
比如我買了一雙鞋,你好奇問我多少錢,我說不超過300元。你還是好奇,你想知道到底多少,我就讓你猜,你會 怎么猜?
答案:你每次猜中間數(shù)。
對吧,所以我們一般猜數(shù)字的時候都從中間猜,再根據(jù)大了或者小了調(diào)整。應用到算法上其實省去了好多麻煩,直接將查找范圍縮小了將近一半,大大提高了運算效率。顧此算法非常高效,以下可供大家了解一下:
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int k = 7;
int left = 0;
int right = sizeof(arr)/sizeof(arr[0])- 1;
int mid = 0;
while (left <= right)
{
mid = left + (right - left) / 2;
if (arr[mid] < k)
{
left = mid + 1;
}
else if (arr[mid]>k)
{
right = mid - 1;
}
else
{
printf("找到了,下標是:%d\n",mid);
break;
}
}
if (left > right)
printf("找不到了\n");
system("pause");
return 0;
}
這個是一個簡單的查找數(shù)組元素的方法,當然后續(xù)小洛會繼續(xù)拓展,比如你輸一個數(shù)組,再次查找你剛才所輸入元素的下標,將再次進行代碼優(yōu)化。當然我們也可以將其設(shè)置為函數(shù),更加方便我們調(diào)用。以下為函數(shù)模型:
int binary_search(int arr[], int k, int sz)
{
int left = 0;
int mid = 0;
int right = sz - 1;
while (left <= right)
{
mid = left + (right - left) / 2;
if (arr[mid] < k)
{
left = mid + 1;
}
else if (arr[mid]>k)
{
right = mid - 1;
}
else
{
return mid;
}
}
return -1;
}
如果我們查找到了這個元素的下標,就直接返回此下標,否則就返回-1。這樣做使代碼更加簡潔,凝練。再附上main函數(shù):
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int k = 7;
int sz = sizeof(arr) / sizeof(arr[0]) - 1;
int ret = binary_search(arr,k ,sz);
if (ret == -1)
{
printf("找不到呀!\n");
}
else
{
printf("找到了,下標是:%d", ret);
}
system("pause");
return 0;
}
當讓我們還可以再進行一下優(yōu)化,這樣使代碼更加靈活。如:
int binary_search(int arr[], int k, int left,int right)
{
int mid = 0;
while (left <= right)
{
mid = left + (right - left) / 2;
if (arr[mid] < k)
{
left = mid + 1;
}
else if (arr[mid]>k)
{
right = mid - 1;
}
else
{
return mid;
}
}
return -1;
}
這樣做我們可以對left和right進行修改,又可以提高一下效率。是不是非常使用呢?
下次小洛將帶來更多知識,和大家一起成長。
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。