C 二分查找 递归与非递归的实现代码

代码如下:

#include <stdio.h>

int binSearch(int arr[], int low, int high, int key);
int binSearch2(int arr[], int low, int high, int key);
int binSearch3(int arr[],int start,int ends,int key);
int main() {
    int arr[]={3,8,11,15,17,22,23,26,28,29,34};
    //printf("%d",binSearch(arr,0,10,26));
    printf("%d",binSearch3(arr,0,10,26));
    return 1;
}

int binSearch(int arr[], int low, int high, int key) {
    int flag=-1;
    int mid = (low + high) / 2;
    if (low > high) {
        flag= -1;
    } else {

if (arr[mid] < key) {
            flag= binSearch(arr, mid + 1, high, key);
        } else if (arr[mid]>key) {
            //比如要找的节点在下面这一层   那么这一层会返回下标上来 用flag接住嘛...
            flag= binSearch(arr,low,mid-1,key);//又差一点忘记了用flag取接住返回值了

} else {
            flag= mid;
        }
    }
    return flag;
}

//ok==============================
int binSearch2(int arr[], int low, int high, int key) {
    int mid = (low + high) / 2;
    if (low > high) {
        return -1;
    } else {

if (arr[mid] < key) {
            return binSearch2(arr, mid + 1, high, key);
        } else if (arr[mid]>key) {
            return binSearch2(arr,low,mid-1,key);
        } else {
            return mid;
        }
    }

}

int binSearch3(int arr[],int start,int ends,int key){
    int mid=-1;
    while(start<=ends){
        mid=(start+ends)/2;
        if(arr[mid]<key){
            start=mid+1;
        }else if(arr[mid]>key){
            ends=mid-1;
        }else{
            break;
        }
    }//上述循环结束后不一定就是 start>ends的  因为有break语句
    if(start>ends){
        mid=-1;
    }
    return mid;
}

赞 (0)

相关推荐

  • c# 二分查找算法

    c# 二分查找算法

    折半搜索,也称二分查找算法.二分搜索,是一种在有序数组中查找某一特定元素的搜索算法. A 搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束: B 如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较. C 如果在某一步骤数组为空,则代表找不到.这种搜索算法每一次比较都使搜索范围缩小一半. 时间复杂度折半搜索每次把搜索区域减少一半,时间复杂度为. (n代表集合中元素的个数)空间复杂度 复制代码 代码如下: //

  • C#二分查找算法实例分析

    本文实例讲述了C#二分查找算法.分享给大家供大家参考.具体实现方法如下: // input array is assumed to be sorted public int BinarySearch(int[] arr, int x) { if (arr.Length == 0) return -1; int mid = arr.Length / 2; if (arr[mid] == x) return mid; if (x < arr[mid]) return BinarySearch(Get

  • C++实现旋转数组的二分查找

    本文实例讲述了C++实现旋转数组的二分查找方法,分享给大家供大家参考.具体方法如下: 题目要求: 旋转数组,如{3, 4, 5, 1, 2}是{1, 2, 3, 4, 5}的一个旋转,要求利用二分查找查找里面的数. 这是一道很有意思的题目,容易考虑不周全.这里给出如下解决方法: #include <iostream> using namespace std; int sequentialSearch(int *array, int size, int destValue) { int pos

  • C++二分查找在搜索引擎多文档求交的应用分析

    本文实例讲述了C++二分查找在搜索引擎多文档求交的应用.分享给大家供大家参考.具体如下: int search2(int array[], int n, int v) { int left, right, middle; left = 0, right = n - 1; while (left <= right) { middle = (left + right) / 2; if (array[middle] > v) { right = middle - 1; } else if (arra

  • C语言使用stdlib.h库函数的二分查找和快速排序的实现代码

    快速排序: 复制代码 代码如下: #include <stdlib.h>#include <stdio.h>#include <string.h> #define LENGTH(x) sizeof(x)/sizeof(x[0]) /**输出数组元素*\param arr:指向数组的指针*\param len:数组元素的个数*/void print(char (*arr)[10],int len){    int i;    for (i=0;i<len;i++) 

  • python二分法查找算法实现方法【递归与非递归】

    本文实例讲述了python二分法查找算法实现方法.分享给大家供大家参考,具体如下: 二分法查找 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表.重复以上过

  • 数据结构 二叉树的递归与非递归

    数据结构 二叉树的递归与非递归 实例代码: #include <iostream> #include <queue> #include <stack> #include <assert.h> using namespace std; template<class T> struct BinaryTreeNode { BinaryTreeNode<T>* _left; BinaryTreeNode<T>* _right; T

  • C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

    C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

    C++ 数据结构二叉树(前序/中序/后序递归.非递归遍历) 二叉树的性质: 二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子. 例: 实例代码: #include <iostream> #include <Windows.h> #include <stack> using namespace std; template <class T> struct BinaryTreeNode { int _data; BinaryTree

  • Java编程二项分布的递归和非递归实现代码实例

    Java编程二项分布的递归和非递归实现代码实例

    本文研究的主要内容是Java编程二项分布的递归和非递归实现,具体如下. 问题来源: 算法第四版 第1.1节 习题27:return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p); 计算递归调用次数,这里的递归式是怎么来的? 二项分布: 定义:n个独立的是/非试验中成功次数k的离散概率分布,每次实验成功的概率为p,记作B(n,p,k). 概率公式:P(ξ=K)= C(n,k) * p^k * (1-p)^(n-k

  • 分析python动态规划的递归、非递归实现

    概要 本文只是简单的介绍动态规划递归.非递归算法实现 案例一 题目一:求数组非相邻最大和 [题目描述] 在一个数组arr中,找出一组不相邻的数字,使得最后的和最大. [示例输入] arr=1 2 4 1 7 8 3 [示例输出] 15 from functools import wraps def memoDeco(func): ''' memoDeco主要是缓存已遍历的节点,减少递归内存开销 ''' cashe={} @wraps(func) def wrapper(*args): if ar

  • JAVA递归与非递归实现斐波那契数列

    斐波那契数列(Fibonacci sequence),又称黄金分割数列.因数学家列昂纳多·斐波那契(Leonardoda Fibonacci[1] )以兔子繁殖为例子而引入,故又称为"兔子数列",指的是这样一个数列:0.1.1.2.3.5.8.13.21.34.--在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)在现代物理.准晶体结构.化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963起

  • java递归与非递归实现扫描文件夹下所有文件

    java扫描指定文件夹下面的所有文件,供大家参考,具体内容如下 扫描一个文件夹下面的所有文件,因为文件夹的层数没有限制可能多达几十层几百层,通常会采用两种方式来遍历指定文件夹下面的所有文件. 递归方式 非递归方式(采用队列或者栈实现) 下面我就给出两种方式的实现代码,包括了递归与非递归实现,code如下所示. java代码: package q.test.filescanner; import java.io.File; import java.util.ArrayList; import ja

  • Java排序算法三之归并排序的递归与非递归的实现示例解析

    归并有递归和非递归两种. 归并的思想是: 1.将原数组首先进行两个元素为一组的排序,然后合并为四个一组,八个一组,直至合并整个数组: 2.合并两个子数组的时候,需要借助一个临时数组,用来存放当前的归并后的两个数组: 3.将临时数组复制回原数组对应的位置. 非递归的代码如下: package mergesort; import java.util.Arrays; import java.util.Random; import java.util.Scanner; //归并排序的非递归算法 publ

  • Java二叉树的四种遍历(递归和非递归)

    Java二叉树的四种遍历(递归和非递归)

    二叉树的遍历可以分为前序.中序.后序.层次遍历. 前中后是指何时访问中间节点,即前序遍历,遍历节点的顺序为:中->左->右: 中序遍历,遍历节点的顺序为:左->中->右: 后序遍历,遍历节点的顺序为:左->右->中. 前序遍历 递归实现 public void preorder_Traversal(TreeNode root) { if(root==null)return; //访问节点的逻辑代码块 System.out.print(root.val+" &q

  • java二叉树的几种遍历递归与非递归实现代码

    java二叉树的几种遍历递归与非递归实现代码

    前序(先序)遍历 中序遍历 后续遍历 层序遍历 如图二叉树: 二叉树结点结构 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x){ val=x; } @Override public String toString(){ return "val: "+val; } } 访问函数 public void visit(TreeNode node){ System.out.print(

随机推荐