例21 折半查找
問題描述
順序查找是一種最簡單和最基本的檢索方法，其基本思想是：從檢索表的一端（如表中第一個記錄或最后一個記錄）開始，逐個進行記錄的關鍵字和給定值的比較，若某個記錄的關鍵字和給定值比較相等，則查找成功；否則，若直至檢索表的另一端（如最后一個記錄或第一個記錄），其關鍵字和給定值比較都不等，則表明表中沒有待查記錄，查找不成功，
順序查找可以寫成一個簡單的一重回圈，回圈中依次將檢索表（不妨設為陣列a）中的元素與給定值比較，若相等，用break退出回圈，演算法描述為：
for (i=0; i< n;i++)
if (a[i]==x) break;
這樣，回圈結束后，若回圈控制變數i小于陣列元素個數n，則查找成功；否則，查找失敗，
順序查找實作簡單，但效率不高，當待查找序列有序時，即各檢索表中元素的次序是按其記錄的關鍵字值的大小順序存盤的，此時采用折半查找會大幅提高查找效率，
折半查找的基本思想是先確定待查資料的范圍（區間），然后逐步縮小范圍直到找到或找不到該記錄為止，具體做法是：先取陣列中間位置的資料元素與給定值比較，若相等，則查找成功；否則，若給定值比該資料元素的值小（或大），則給定值必在陣列的前半部分（或后半部分），然后在新的查找范圍內進行同樣的查找，如此反復進行，直到找到陣列元素值與給定值相等的元素或確定陣列中沒有待查找的資料為止，因此，折半查找每查找一次，或成功，或使查找陣列中元素的個數減少一半，當查找陣列中不再有資料元素時，查找失敗，
輸入一個整數，在給定的有序陣列中查找該整數是否存在，若存在，給出其陣列的下標；若不存在，輸出查找不成功資訊，
輸入格式
第一行是一個正整數N (1 ≤ N ≤ 100000)，代表陣列中元素的個數，
第二行有N個整數，這N個整數從小到大排列好了，
第三行是一個整數M，代表待查找元素的個數，
接下來的M行，每行有一個整數x，表示每個待查找的元素，
輸出格式
輸出有M行，每行一個整數，若待查找元素x在陣列中存在，輸出其陣列元素的下標；若不存在，輸出-1，
輸入樣例
20
1 6 9 14 15 17 18 23 24 28 34 39 48 56 67 72 89 92 98 100
3
1
25
72
輸出樣例
0
-1
15
（1）編程思路，
設有一陣列a[n]，陣列中的元素按值從小到大排列有序，用變數low、high和mid分別指示待查元素所在區間的下界、上界和中間位置，初始時，low=0，high=n-1，
1）令 mid = (low+ high) /2 ，
2）比較給定值x與a[mid]值的大小
若a[mid] == x ，則查找成功，結束查找；
若a[mid]> x ，則表明給定值x只可能在區間low ~ mid-1內，修改檢索范圍，令high=mid-1，low值保持不變；
若a[mid]< x ，則表明給定值x只可能在區間mid+1~high內，修改檢索范圍，令low=mid+1，high值保持不變，
3）比較當前變數low和high的值，若low≤high，重復執行第1）、2）兩步，若low>high，表明陣列中不存在待查找的元素，查找失敗，
例如，設一有序的陣列中有11個資料元素，它們的值依次為{3，8，15，21，35，54，63，79，82，92，97}，用折半查找在該陣列中查找值為82和87的元素的程序如圖1所示，
圖1 折半查找的查找程序
圖1（a）所示為查找成功的情況，僅需比較2次，若用順序查找，則需比較9次，圖1（b）所示為查找不成功的情況，此時因為low>high，說明陣列中沒有元素值等于87的元素，得到查找失敗資訊，也只需比較4次，若用順序查找，則必須比較12次，
折半查找程序通常可用一個二叉判定樹表示，對于上例給定長度的陣列，折半查找程序可用圖2所示的二叉判定樹來描述，樹中結點的值為相應元素在陣列中的位置，查找成功時恰好走了一條從根結點到該元素相應結點的路徑，所用的比較次數是該路徑長度加1或結點在二叉判定樹上的層次數，所以，折半查找在查找成功時所用的比較次數最多不超過相應的二叉判定樹的深度[log2n]+ 1，同理，查找不成功時，恰好走了一條從根結點到某一終端結點的路徑，因此，所用的比較次數最多也不超過[log2n] + 1，
圖2 描述折半查找程序的二叉判定樹
（2）源程式，
#include <stdio.h>
#define N 100001
int main()
{
int a[N],n;
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d",&a[i]);
int m;
scanf("%d",&m);
while (m--)
{
int x;
scanf("%d",&x);
int low =0, high =n-1,mid; // 置區間初值
while (low<=high)
{
mid = (low+high)/2 ;
if (x == a[mid]) break; // 找到待查記錄
else if (x<a[mid]) high=mid-1; // 繼續在前半區間進行檢索
else low=mid+1; // 繼續在后半區間進行檢索
}
if (low<=high) // 找到待查記錄
printf("%d\n",mid);
else
printf("-1\n");
}
return 0;
}
習題21
21-1 Can you find it?
本題選自杭州電子科技大學OJ題庫（http://acm.hdu.edu.cn/showproblem.php?pid=2141）
Problem Description
Give you three sequences of numbers A, B, C, then we give you a number X. Now you need to calculate if you can find the three numbers Ai, Bj, Ck, which satisfy the formula Ai+Bj+Ck = X.
Input
There are many cases. Every data case is described as followed: In the first line there are three integers L, N, M, in the second line there are L integers represent the sequence A, in the third line there are N integers represent the sequences B, in the forth line there are M integers represent the sequence C. In the fifth line there is an integer S represents there are S integers X to be calculated. 1<=L, N, M<=500, 1<=S<=1000. all the integers are 32-integers.
Output
For each case, firstly you have to print the case number as the form "Case d:", then for the S queries, you calculate if the formula can be satisfied or not. If satisfied, you print "YES", otherwise print "NO".
Sample Input
3 3 3
1 2 3
1 2 3
1 2 3
3
1
4
10
Sample Output
Case 1:
NO
YES
NO
（1）編程思路，
本題的題意是：有A、B、C三個陣列，每個陣列中有若干個整數元素，要求判斷對于輸入的整數x，是否可以在A、B、C三個陣列中各取一個元素，使得三個元素之和等于x，若可以取得，輸出“YES”，否則輸出“NO”，
預先求出陣列A和B中任意各取一個數相加所得到的和值，存盤到q陣列中，然后對q陣列進行排序，排序后去掉陣列q中重復的和值，
對于輸入的X，列舉陣列C中的每個元素C[i]，然后在q陣列中采用折半查找是否存在X-C[i]，若存在，則輸出“YES”，否則輸出“NO”，
（2）源程式，
#include <stdio.h>
#include<algorithm>
using namespace std;
#define N 501
int binsearch(int a[],int n,int key);
int main()
{
int a[N],b[N],c[N];
int q[N*N];
int cnt=0,l,m,n;
while(scanf("%d%d%d",&l,&m,&n)!=EOF)
{
int i,j,k;
for (i=0;i<l;i++) scanf("%d",&a[i]);
for (i=0;i<m;i++) scanf("%d",&b[i]);
for (i=0;i<n;i++) scanf("%d",&c[i]);
k=0;
for (i=0;i<l;i++)
for (j=0;j<m;j++)
q[k++]=a[i]+b[j];
sort(q,q+k);
for (i=j=1;i<k;i++)
if (q[i]!=q[j]) q[j++]=q[i]; // 去重
k=j;
printf("Case %d:\n",++cnt);
int s,x;
scanf("%d",&s);
for(i=1;i<=s;i++)
{
scanf("%d",&x);
for(j=0;j<n;j++)
if (binsearch(q,k,x-c[j])!=-1) break;
printf("%s\n",(j<n)?"YES":"NO");
}
}
return 0;
}
int binsearch(int a[],int n,int key)
{
int low =0,high =n-1;
while (low<=high)
{
int mid = (low+high)/2 ;
if (key==a[mid]) return mid; // 找到待查記錄
else if (key<a[mid]) high=mid-1; // 繼續在前半區間進行檢索
else low=mid+1; // 繼續在后半區間進行檢索
}
return -1; // 找不到待查記錄
}
21-2 木材加工
本題選自洛谷題庫 （https://www.luogu.org/problem/P2440）
題目描述
木材廠有一些原木，現在想把這些木頭切割成一些長度相同的小段木頭（木頭有可能有剩余），需要得到的小段的數目是給定的，當然，我們希望得到的小段木頭越長越好，你的任務是計算能夠得到的小段木頭的最大長度，木頭長度的單位是cm，原木的長度都是正整數，我們要求切割得到的小段木頭的長度也是正整數，
例如有兩根原木長度分別為11和21，要求切割成到等長的6段，很明顯能切割出來的小段木頭長度最長為5.
輸入格式
第一行是兩個正整數N和K(1 ≤ N ≤ 100000，1 ≤ K ≤ 100000000)，N是原木的數目，K是需要得到的小段的數目，
接下來的N行，每行有一個1到100000000之間的正整數，表示一根原木的長度，
輸出格式
能夠切割得到的小段的最大長度，如果連1cm長的小段都切不出來，輸出”0”，
輸入樣例
3 7
232
124
456
輸出樣例
114
（1）編程思路，
這個問題可以采用類似于折半查找的方法進行解決，
設left是切割的小段木頭的最短長度，right是最大長度，初始時，left為1，right為最長的原木長度，
每次取left和right的中間值mid（mid = (left + right) / 2）進行嘗試，測驗采用當前長度mid進行加工，能否切割出需要的段數K，測驗演算法描述為：
num = 0;
for (i = 0; i < n; i++)
{
if (num >= k) break;
num = num + len[i] / mid ;
}
如果當前mid值可以加工出所需段數（即num >= k），就增大mid值繼續試（通過讓left = mid的方法來增大mid），不符合要求就減小mid值繼續試（通過讓right = mid的方法來減小mid），直到left + 1 >= right結束嘗試，所得的left值就是可以加工出的小段木頭的最大長度，
（2）源程式，
#include <stdio.h>
int main()
{
int n, k, len[100001], i, left, right, mid,num;
scanf("%d%d",&n,&k);
right = 0;
int sum=0;
for (i = 0; i < n; i++)
{
scanf("%d",&len[i]);
sum+=len[i];
if (right < len[i]) right = len[i];
}
if (sum<k)
{
printf("0\n");
return 0;
}
left =1 ;
while ( left + 1 < right)
{
mid = (left + right) / 2;
num = 0;
for (i = 0; i < n; i++)
{
if (num >= k) break;
num = num + len[i] / mid ;
}
if ( num >= k )
left = mid;
else
right = mid;
}
printf("%d\n",left);
return 0;
}
21-3 xx的位數
題目描述
使得 xx 達到或超過 n 位數字的最小正整數 x 是多少？
輸入格式
一個正整數 n（n<=2000000000），
輸出格式
使得 xx達到 n 位數字的最小正整數 x，
輸入樣例
11
輸出樣例
10
（1）編程思路，
正整數m的位數為[log10(m)]+1 ([ ]表示向下取整），
本題求x^x的位數，也就是求[log10(x^x)]+1，利用對數的運演算法則，log10(x^x)=x* log10(x)，由于對數函式滿足單調遞增，因此可采用二分的思想求x* log10(x)≥n-1的最小值，
初始時，設left為1，right為最大整數2e9，
每次取left和right的中間值mid（mid = (left + right) / 2）進行嘗試，看當前數mid^mid的位數是否達到或超過n，
如果當前mid^mid的位數小于n（即mid*log10(mid)<n），說明mid小了，就增大mid值繼續試（通過讓left = mid+1的方法來增大mid），若當前mid^mid的位數不小于n（即mid*log10(mid)>=n），說明mid值符合要求，但為了找到其最小值，就減小mid值繼續試（通過讓right = mid的方法來減小mid），直到left >= right結束嘗試，所得的left值就是可以使得 xx 達到或超過 n 位數字的最小正整數 x，
（2）源程式，
#include <stdio.h>
#include <math.h>
int main()
{
int n;
scanf("%d",&n);
n--;
int left=1,right=2e9;
while (left<right)
{
int mid=(left+right)/2;
if (mid*log10(mid)<n) left=mid+1;
else right=mid;
}
printf("%d\n",left);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/59750.html
標籤：C