C语言编程中实现二分查找的简单入门实例

架设有一个数组 v 已经按升序排列了，数组 v 有 n=20 个元素。数组中有个元素 x，如何知道 x 位于该数组的第几位呢？
解决这个问题的一个普遍方法就是二分查找法。下面是程序：

#include <stdio.h>
int binsearch(int x, int v[], int n);
main()
{
  int i, result, n;
 int wait;

  int x = 17; // 需要查找的数值
 int v[19]; // 定义一个数组
 // 给数组赋值
 for(i = 0; i < 20; ++i)
   v[i] = i;
 /**
 for(i = 0; i < 20; ++i)
 printf("%d \n", v[i]);
 */
 n = 20;
 result = binsearch(x, v, n);
 printf("%d", result);
 scanf("%d", &wait);
}
int binsearch(int x, int v[], int n)
{
 int low, high, mid;
 low = 0;
 high = n - 1;
 while (low <= high)
 {
 mid = (low + high) / 2;
 if(x < v[mid])
  high = mid - 1;
 else if (x > v[mid])
  low = mid + 1;
 else
  return mid;
 // 看看循环执行了多少次
 printf("mid = %d, low = %d, high = %d \n", mid, low, high);
 }
 return -1;
}

1、二分查找法

二分查找法有一个很重要的前提条件：即待查找的序列必须是已经排好序的。

假设元素序列是按升序排列，将序列中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将序列分成前、后两个子序列，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子序列，否则进一步查找后一子序列。重复以上过程，直到找到满足条件的记录，查找成功，返回元素在序列中的索引，或直到子序列不存在为止，此时查找失败，返回-1。

int find2(int *array,int n,int val)
{
  if (n<=0)
  {
    return -1;
  } 

  int begin=0,end=n-1,mid;
  while(begin<=end)
  {
    mid=(begin+end)/2;
    if (array[mid]==val)
      return mid;
    else if(array[mid]>val)
      end=mid-1;
    else
      begin=mid+1;
  } 

  return -1;
}

2、使用二分查找树查找

首先创建一颗二分查找树，我们知道二分查找树的特点是左子树的值都比根节点小，右子树的值都比根节点大，且二分查找树的中序遍历所得到的元素是排好序的。

//二叉查找树数据结构
typedef struct Btree
{
  int data;
  Btree *left;
  Btree *right;
}*PBTree; 

//创建二叉查找树，返回树的根节点
PBTree CreateBTree(int *array,int n)
{
  PBTree root=new Btree;
  root->data=array[0];
  root->left=NULL;
  root->right=NULL; 

  PBTree current,back,pNew;
  for (int i=1;i<n;i++)
  {
    pNew=new Btree;
    pNew->data=array[i];
    pNew->left=pNew->right=NULL;
    current=root;
    while(current!=NULL)  //找到合适的插入位置
    {
      back=current;
      if(current->data>array[i])
        current=current->left;
      else
        current=current->right;
    }
    if(back->data>array[i])
      back->left=pNew;
    else
      back->right=pNew;
  } 

  return root;
} 

//利用二叉查找树进行递归查找
bool find3(PBTree root,int val)
{
  if (root==NULL)
    return false;
  if (root->data==val)
    return true;
  else if(root->data>val)
    return find3(root->left,val);
  else
    return find3(root->right,val);
}

3、总结

二分查找有非常严格的限制条件（序列必须是有序的）；

而使用二分查找树，则会自动创建出"有序树"（中序遍历得到的序列是有序的）；

不考虑二叉查找树的建立时间，二者的效率一样，均为O（logn）。

赞 (0)

相关推荐

  • 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++实现旋转数组的二分查找

    本文实例讲述了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++程序中的应用示例

    二分查找算法的思想很简单,<编程珠玑>中的描述: 在一个包含t的数组内,二分查找通过对范围的跟综来解决问题.开始时,范围就是整个数组.通过将范围中间的元素与t比较并丢弃一半范围,范围就被缩小.这个过程一直持续,直到在t被发现,或者那个能够包含t的范围已成为空.         Donald Knuth在他的<Sorting and Searching>一书中指出,尽管第一个二分查找算法早在1946年就被发表,但第一个没有bug的二分查找算法却是在12年后才被发表出来.其中常见的一个

  • 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++) 

  • C++二分法在数组中查找关键字的方法

    本文实例讲述了C++二分法在数组中查找关键字的方法.分享给大家供大家参考.具体如下: /* 此程序演示了二分法查找算法(针对按从小到大排列的数组)的实现. */ #include <iostream> using namespace std; /* 功能: 实现数组的二分法查找(只算法只适合按从小到大排列的数组) 返回值:关键字在数组中的下标, 返回-1表示未找到 a[]: 要搜索的数组 len: 数组元素个数 key: 要查找的关键字 */ int binSearch(int a[], in

  • C语言编程中实现二分查找的简单入门实例

    架设有一个数组 v 已经按升序排列了,数组 v 有 n=20 个元素.数组中有个元素 x,如何知道 x 位于该数组的第几位呢? 解决这个问题的一个普遍方法就是二分查找法.下面是程序: #include <stdio.h> int binsearch(int x, int v[], int n); main() { int i, result, n; int wait; int x = 17; // 需要查找的数值 int v[19]; // 定义一个数组 // 给数组赋值 for(i = 0;

  • 在MySQL中实现二分查找的详细教程

    给定一个升序排列的自然数数组,数组中包含重复数字,例如:[1,2,2,3,4,4,4,5,6,7,7].问题:给定任意自然数,对数组进行二分查找,返回数组正确的位置,给出函数实现.注:连续相同的数字,返回第一个匹配位置还是最后一个匹配位置,由函数传入参数决定. 我为什么会出这道题目? 二分查找在数据库内核实现中非常重要 在数据库的内核实现中,二分查找是一个非常重要的逻辑,几乎99%以上的SQL语句(所有索引上的范围扫描/等值查询/Unique查询等),都会使用到二分查找进行数据的定位. 考虑一个

  • C语言编程中常见的五种错误及对应解决方案

    目录 1. 未初始化的变量 2. 数组越界 3. 字符串溢出 4. 重复释放内存 5. 使用无效的文件指针 前言: C 语言有时名声不太好,因为它不像近期的编程语言(比如 Rust)那样具有内存安全性.但是通过额外的代码,一些最常见和严重的 C 语言错误是可以避免的. 即使是最好的程序员也无法完全避免错误.这些错误可能会引入安全漏洞.导致程序崩溃或产生意外操作,具体影响要取决于程序的运行逻辑. 下文讲解了可能影响应用程序的五个错误以及避免它们的方法: 1. 未初始化的变量 程序启动时,系统会为其

  • js基本算法:冒泡排序,二分查找的简单实例

    知识扩充: 时间复杂度:算法的时间复杂度是一个函数,描述了算法的运行时间.时间复杂度越低,效率越高. 自我理解:一个算法,运行了几次时间复杂度就为多少,如运行了n次,则时间复杂度为O(n). 1.冒泡排序 解析:1.比较相邻的两个元素,如果前一个比后一个大,则交换位置. 2.第一轮的时候最后一个元素应该是最大的一个. 3.按照步骤一的方法进行相邻两个元素的比较,这个时候由于最后一个元素已经是最大的了,所以最后一个元素不用比较. function sort(elements){ for(var i

  • java数据结构之二分查找法 binarySearch的实例

    java数据结构之二分查找法 binarySearch的实例 折半查找法,前提是已经排好序的数组才可查找 实例代码: public class BinarySearch { int[] bArr; public void setArr(int[] bArr){ this.bArr=bArr; } public static void main(String[] args) { int arrLength=16; int[] bArr=new int[arrLength]; System.out.

  • Java二分查找算法实现代码实例

    这篇文章主要介绍了Java二分查找算法实现代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 二分查找: 两种方式: 非递归方式和递归方式 主要思路: 对于已排序的数组(先假定是从小到大排序), 先定义两个"指针", 一个"指向"首元素low, 一个"指向"末尾元素high. 然后, 开始折半比较, 即让要查找的数与数组中间的元素(索引为 low+high/2)比较. 若要查找的数比中间数小

  • 初步剖析C语言编程中的结构体

    C语言结构体,可谓是C强大功能之一,也是C++语言之所以能衍生的有利条件,事实上,当结构体中成员中有函数指针了后,那么,结构体也即C++中的类了. C语言中,结构体的声明.定义是用到关键字struct,就像联合体用到关键字union.枚举类型用到enum关键字一样,事实上,联合体.枚举类型的用法几乎是参照结构体来的.结构体的声明格式如下: struct tag-name{ { member 1; - member N; }; 因此,定义结构体变量的语句为:struct tag-name vari

  • 详解C语言编程中预处理器的用法

    预处理最大的标志便是大写,虽然这不是标准,但请你在使用的时候大写,为了自己,也为了后人. 预处理器在一般看来,用得最多的还是宏,这里总结一下预处理器的用法. #include <stdio.h> #define MACRO_OF_MINE #ifdef MACRO_OF_MINE #else #endif 上述五个预处理是最常看见的,第一个代表着包含一个头文件,可以理解为没有它很多功能都无法使用,例如C语言并没有把输入输入纳入标准当中,而是使用库函数来提供,所以只有包含了stdio.h这个头文

  • 一篇文章带你了解C语言二分查找的简单应用

    一篇文章带你了解C语言二分查找的简单应用

    目录 前言 实战演练 思路分析 总结 前言 在有序数组中查找具体的某个数字n,可能有同学会说一个一个找,但是这样的效率实在太低,特别是对于有序的数组,效率太低.我们一般从中间元素开始找,查一次去掉一半数字,这种方法我们给它取名为折半查找即为二分查找,效率大大提高!怎么理解呢?如果有2的32次方个数字,我们最多只需查找32次,而一个一个数运气不好却是2的32次方次. 实战演练 这里我们先给出所写代码以及运行结果 在这里,给大家分析一下,首先,我们先创建一个有序数组arr[],然后我们把要查找的7用

  • LintCode-排序列表转换为二分查找树分析及实例

    给出一个所有元素以升序排序的单链表,将它转换成一棵高度平衡的二分查找树 您在真实的面试中是否遇到过这个题? 分析:就是一个简单的递归,只是需要有些链表的操作而已 代码: /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } * Defin

随机推荐