服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C语言编程中实现二分查找的简单入门实例

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

2021-03-17 15:05dazhong159 C/C++

这篇文章主要介绍了C语言编程中实现二分查找的简单入门实例,需要的朋友可以参考下

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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。

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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、使用二分查找树查找

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//二叉查找树数据结构
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)。

延伸 · 阅读

精彩推荐
  • C/C++C语言中炫酷的文件操作实例详解

    C语言中炫酷的文件操作实例详解

    内存中的数据都是暂时的,当程序结束时,它们都将丢失,为了永久性的保存大量的数据,C语言提供了对文件的操作,这篇文章主要给大家介绍了关于C语言中文件...

    针眼_6702022-01-24
  • C/C++深入理解goto语句的替代实现方式分析

    深入理解goto语句的替代实现方式分析

    本篇文章是对goto语句的替代实现方式进行了详细的分析介绍,需要的朋友参考下...

    C语言教程网7342020-12-03
  • C/C++C++之重载 重定义与重写用法详解

    C++之重载 重定义与重写用法详解

    这篇文章主要介绍了C++之重载 重定义与重写用法详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...

    青山的青6062022-01-04
  • C/C++详解c语言中的 strcpy和strncpy字符串函数使用

    详解c语言中的 strcpy和strncpy字符串函数使用

    strcpy 和strcnpy函数是字符串复制函数。接下来通过本文给大家介绍c语言中的strcpy和strncpy字符串函数使用,感兴趣的朋友跟随小编要求看看吧...

    spring-go5642021-07-02
  • C/C++c++ 单线程实现同时监听多个端口

    c++ 单线程实现同时监听多个端口

    这篇文章主要介绍了c++ 单线程实现同时监听多个端口的方法,帮助大家更好的理解和学习使用c++,感兴趣的朋友可以了解下...

    源之缘11542021-10-27
  • C/C++C/C++经典实例之模拟计算器示例代码

    C/C++经典实例之模拟计算器示例代码

    最近在看到的一个需求,本以为比较简单,但花了不少时间,所以下面这篇文章主要给大家介绍了关于C/C++经典实例之模拟计算器的相关资料,文中通过示...

    jia150610152021-06-07
  • C/C++C语言实现电脑关机程序

    C语言实现电脑关机程序

    这篇文章主要为大家详细介绍了C语言实现电脑关机程序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...

    xiaocaidayong8482021-08-20
  • C/C++学习C++编程的必备软件

    学习C++编程的必备软件

    本文给大家分享的是作者在学习使用C++进行编程的时候所用到的一些常用的软件,这里推荐给大家...

    谢恩铭10102021-05-08