遞歸演算法實現二分查找

⑴ python 二分查找演算法函數bi_search(),該函數實現檢索任意一個整數在 prime() 函數生成的

defprime(n):
ifn<=2:
return[]
result=[False,False]+[True]*(n-2)
foriinrange(len(result)):
ifresult[i]==True:
forjinrange(2*i,len(result),i):
result[j]=False
return[iforiinrange(len(result))ifresult[i]==True]
defbi_search(prime,primelist,start,end):
ifstart>end:
return-1
mid=(start+end)//2
ifprimelist[mid]==prime:
returnmid
elifprimelist[mid]>prime:
end=mid-1
else:
start=mid+1
returnbi_search(prime,primelist,start,end)
if__name__=='__main__':
n=int(raw_input())
primelist=prime(n)
num=raw_input()
whilenum:
num=int(num)
index=bi_search(num,primelist,0,len(primelist)-1)
print(index)
num=raw_input()

⑵ c++二分查找（遞歸法）為什麼答案錯誤

數組的i未經賦值。聲明的數組是不確定的。

其實，程序沒有使用題目規定的二分查找，和遞歸的方法。

#include<cstdio>
inta[1000000];
intbsearch(intlow,inthigh,intx)
{intm;
if(low>high)return-1;
m=(low+high)/2;
if(a[m]==x)returnm+1;
if(a[m]>x)returnbsearch(low,m-1,x);
elsereturnbsearch(m+1,high,x);
}
usingnamespacestd;
intmain()
{intn=10,x,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&x);
printf("%d
",bsearch(0,n-1,x));
return0;
}

⑶ 編寫一個在有序表中二分查找給定關鍵字記錄的遞歸演算法 (C語言)

其實這個書本上可以找到的，邏輯也比較容易實現。我寫一下主要的邏輯吧。
int Serch(int * a, int low, int high. int key)
{
if (low <= high)
{

int mid = ( high - low) / 2 + low;
if (key == a[mid]) // 找到了

return mid;
else if (key < a[mid]) // 比中間值小，向前找

Serch(a, low, mid - 1, key);
else // 向後找

Serch(a, mid + 1, high, key);

}
return -1; // 沒找到

}

⑷ 用遞歸方法寫出有序數組的二分查找演算法

什麼是二分查找？

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。

二分查找優缺點

優點是比較次數少，查找速度快，平均性能好；

其缺點是要求待查表為有序表，且插入刪除困難。

因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。
使用條件：查找序列是順序結構，有序。

過程

首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

利用循環的方式實現二分法查找

public class BinarySearch {
public static void main(String[] args) {
// 生成一個隨機數組 int[] array = suiji();
// 對隨機數組排序 Arrays.sort(array);
System.out.println("產生的隨機數組為： " + Arrays.toString(array));

System.out.println("要進行查找的值： ");
Scanner input = new Scanner(System.in);
// 進行查找的目標值 int aim = input.nextInt();

// 使用二分法查找 int index = binarySearch(array, aim);
System.out.println("查找的值的索引位置： " + index);

}

/** * 生成一個隨機數組 *
* @return 返回值，返回一個隨機數組 */
private static int[] suiji() {
// random.nextInt(n)+m 返回m到m+n-1之間的隨機數 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循環遍歷為數組賦值 for (int i = 0; i < array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}

/** * 二分法查找 ---循環的方式實現 *
* @param array 要查找的數組 * @param aim 要查找的值 * @return 返回值，成功返回索引，失敗返回-1 */
private static int binarySearch(int[] array, int aim) {
// 數組最小索引值 int left = 0;
// 數組最大索引值 int right = array.length - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
// 若查找數值比中間值小，則以整個查找范圍的前半部分作為新的查找范圍 if (aim < array[mid]) {
right = mid - 1;
// 若查找數值比中間值大，則以整個查找范圍的後半部分作為新的查找范圍 } else if (aim > array[mid]) {
left = mid + 1;
// 若查找數據與中間元素值正好相等，則放回中間元素值的索引 } else {
return mid;
}
}
return -1;
}}
運行結果演示：

總結：

遞歸相較於循環，代碼比較簡潔，但是時間和空間消耗比較大，效率低。在實際的學習與工作中，根據情況選擇使用。通常我們如果使用循環實現代碼只要不是太繁瑣都選擇循環的方式實現~

⑸ C語言 二分查找演算法 用遞歸實現 我改動了一下

本人直接打出來的，並未在平台上編譯運行過，所以可能會有語法錯位，還請自行調試更改
#include<stdio.h>

int RecorBinarySearch(int a[], int, int, int);
int main(void)
{
int i=0, n, m, key;
int a[10000], c[10000];

scanf("%d", &n);
scanf("%d", &m);

printf("提示：輸入%d個整數且必須按升序排列。\n", n);
for(i=0; i<n; i++){
scanf("%d", &a[i]);
}
printf("提示：輸入%d個預查找的數。\n", m);
for(i=0; i<m; i++){
scanf("%d", &key);
c[i] = RecorBinarySearch(a, key, 0, n-1);
}
printf("提示：輸出預查找的數在數組中的位置。（-1代表未找到）\n");
for(i=0; i<m; i++) {
printf("%d ", c[i]);
}
return 0;
}

int RecorBinarySearch(int a[], int key, int low, int high)
{
int nRet;
if(low > high)
nRet = -1;
else {
int mid = (high + low) / 2;
if(key == a[mid])
nRet = mid;
else if(key > a[mid])
nRet = RecorBinarySearch(a, key, mid+1, high);
else if(key < a[mid])
nRet = RecorBinarySearch(a, key, low, mid-1);
}
return nRet;
}

⑹ 用C語言編寫非遞歸演算法實現折半查找（二分查找）

char
a[10][5];//按字典序遞增
int
search(char
*x)//二分查找，返回有序表中大於等於x的元素位置
{
int
low=0,high=9,mid,t;
while(low<=high)
{
mid=(low+high)/2;
t=strcmp(a[mid],x);//比較中點位置與x
if(t==0)
return
mid;//相等返回其位置
else
if(t>0)
high=mid-1;//x小於mid元素，則在中點前
else
low=mid+1;
}
return
high+1;//返回大於x的第一個元素
}
這個是我曾經用過的字元串的二分查找~
請根據需要修改數據類型。。。

⑺ C語言折半查找之遞歸演算法

T的elem沒初始化，沒有申請內存空間。
而且Create的參數T必須要用引用傳遞，不然main中執行完Create(T,a)後，T的值不會變化 。

void Create(SSTable &T,int a[]){
int j;
T.elem=new ch[len(a)];
for(j=1;j<len(a)+1;j++)T.elem[j].key=a[j];
T.length=len(a);
}