二分查找演算法遞歸
㈠ 用遞歸方法寫出有序數組的二分查找演算法
什麼是二分查找？
二分查找也稱折半查找（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;
}}
運行結果演示：
總結：
遞歸相較於循環，代碼比較簡潔，但是時間和空間消耗比較大，效率低。在實際的學習與工作中，根據情況選擇使用。通常我們如果使用循環實現代碼只要不是太繁瑣都選擇循環的方式實現~
㈡ 二分法和二分檢索，還有拆班查找各自之間有什麼區別和聯系啊有誰有二分檢索的遞歸演算法啊
http://..com/question/26674719.html
這個遞歸的二分查找是我寫的，可以參考一下
㈢ 遞歸查找是二分查找嗎
遞歸是遞歸，二分是二分，兩者沒有絕對的關系
二分是搜索演算法，遞歸是實現方法
你可以用遞歸實現二分，也可以用循環實現二分搜索
㈣ 編寫一個在有序表中二分查找給定關鍵字記錄的遞歸演算法 (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; // 沒找到
}
㈤ 二分查找演算法
前提要求數據排好序，有遞歸和非遞歸版本
int binSearch(const int *Array,int start,int end,int key)
{
int left,right;
int mid;
left=start;
right=end;
while (left<=right) { /注釋中為遞歸演算法，執行效率低，不推薦
mid=(left+right)/2;
/* if (key<Array[mid]) {
return(binSearch(Array,left,mid,key));
}
else if(key>Array[mid]){
return (binSearch(Array,mid+1,right,key));
}
else
return mid;
*/
if (key<Array[mid]) {
right=mid-1;
}
else if(key>Array[mid]){
left=mid+1;
}
else
return mid;
}
return -1;
}
㈥ C語言遞歸函數如何實現二分搜索演算法
折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，採用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，已知一個有n個元素的有序序列, 將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，演算法終止。如果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這里假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜索x, 直到找到x或者是沒有找到!
如果是常規的方法的話那麼我們可以通過循環的方式, 按照上面說的演算法, 找到則退出循環, 否則繼續循環直到左下標位置小於或者等於右下標的位置.
按兄弟你的意思是要用遞歸方法進行搜索, 那麼大概還是上面的演算法, 只是把循環的方式改成遞歸方式: 如果沒找到,則確定新的搜索范圍, 即左右下標新位置, 然後把新的參數傳給函數繼續調用函數進行遞歸搜索!!
遞歸方式實現詳細代碼如下:
#include <stdio.h>
#define ARRAY_SIZE 10
#define NOT_FOUND -1
int BinarySearch(int array[], int left, int right, int NumToSearch)
{
int mid = (left + right) / 2;
if (left <= right)
{
if (NumToSearch == array[mid])
{
return mid;
}
else if (NumToSearch < array[mid])
{
right = mid - 1;
return BinarySearch(array, left, right, NumToSearch);
}
else
{
left = mid + 1;
return BinarySearch(array, left, right, NumToSearch);
}
}
return NOT_FOUND;
}
int main()
{
int a[ARRAY_SIZE] = {2, 5, 6, 7, 13, 20, 22, 27, 112, 222};//假設一個已知的有序且是升序數列
int result = 0;//查找的結果
int x = 13;//假設我們要查找的數是13
int left = 0;//序列開始下標
int right = ARRAY_SIZE - 1;//序列結尾下標
result = BinarySearch(a, left, right, x);
if (result == NOT_FOUND)
{
printf("Not Found!\n");
}
else
{
printf("Found %d in array a, it is a[%d]\n", x, result);
}
return 0;
}
希望對兄弟你有幫助!
㈦ 《編程珠璣》一道練習題：二分查找的遞歸演算法，要求函數名為int binarysearch(DataType x[], int n)。
int binarysearch(DataType x[],int n)
{
int low = 0;
int high = n-1,mid;
while(low<high)
{
mid = (low + high)/2;
if(x[mid]<n) low = mid+1;
else if(x[mid]>n) high = 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;
}