C++实现折半查找

2026-04-20 20:42:00

本文实例为大家分享了C++实现折半查找的具体代码，供大家参考，具体内容如下

折半查找

定义：

计算机科学中，折半搜索（英语：half-interval search），也称二分搜索（英语：binary search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

代码：

#include <iostream>
using namespace std;

int Search_Bin(int A[],int key,int n){
 int low = 0;
 int high = n-1;
 int mid;
 while(low<=high){
 mid=(low+high)/2;
 if(key==A[mid]){
  return mid;
 }
 else if(key<A[mid]){
  high=mid-1;
 }
 else{
  low=mid+1;
 }
 }
 return 0;
}

void sort(int A[],int n){
 //冒泡法排序
 for(int i=0;i<n-1;i++){
 for(int j=0;j<n-i-1;j++){
  if(A[j]>A[j+1]){
  int t=A[j];
  A[j]=A[j+1];
  A[j+1]=t;
  }
 }
 }
}

void Print(int A[],int n){
 for(int i=0;i<n;i++){
 cout<<A[i]<<" ";
 }
 cout<<endl;
}
int main()
{
 int A[10]={2,1,4,6,7,3,8,0,5,9};
 Print(A,10);
 sort(A,10);
 Print(A,10);
 cout<<Search_Bin(A,7,10)+1;
 return 0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

C++ 先对数组排序,在进行折半查找

第一步:输入15个整数第二步:对这15个数进行排序第三部:输入一个数,在后在排好序的数中进行折半查找,判断该数的位置实现代码如下: 方法一: 选择排序法+循环折半查找法复制代码代码如下: #include<iostream>using namespace std;int main(){ int a[15]; int n,i; void array_sort(int a[], int n); int zeban(int a[], int start ,int end,int n); c
C++二分查找(折半查找)算法实例详解

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

java 算法二分查找与折半查找折半查找 :首先数组是已经排好序的实例代码: package com.hao.myrxjava; /** * 折半查找 :首先数组是已经排好序的 * * @author zhanghaohao * @date 2017/5/15 */ public class HalfDivision { /** * 循环实现 * * @param array 排好序的数组 * @param value 查找的值 * @return value在array的位置 */ pu
Java 选择、冒泡排序、折半查找(实例讲解)

如下所示: //选择排序对数据进行升序排序 public static void selectSortArray(int[] arr){ for(int i = 0; i<arr.length-1;i++){ for(int j = i+1;j<arr.length;j++){ if(arr[i]>arr[j]){ int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } } } //冒泡排序对数据进行升序排序 public stati
javascript 折半查找字符在数组中的位置(有序列表)

复制代码代码如下: /** * 折半查找字符在数组中的位置(有序列表) * @param array 被检索的数组 * @param x 要查找的字符 * @type int * @returns 字符在数组中的位置,没找到返回-1 */ function binarySearch(array,x){ var lowPoint=1; var higPoint=array.length; var returnValue=-1; var midPoint; var found=false; whi
python实现折半查找和归并排序算法

今天依旧是学算法,前几天在搞bbs项目,界面也很丑,评论功能好像也有BUG.现在不搞了,得学下算法和数据结构,笔试过不了,连面试的机会都没有-- 今天学了折半查找算法,折半查找是蛮简单的,但是归并排序我就挺懵比,看教材C语言写的归并排序看不懂,后来参考了别人的博客,终于搞懂了. 折半查找先看下课本对于折半查找的讲解.注意了,折半查找是对于有序序列而言的.每次折半,则查找区间大约缩小一半.low,high分别为查找区间的第一个下标与最后一个下标.出现low>high时,说明目标关键字在整个有序
基于JavaScript实现的折半查找算法示例

本文实例讲述了基于JavaScript实现的折半查找算法.分享给大家供大家参考,具体如下: 折半查找也叫做二分查找,是针对有序表的一种查找方式,其思想如下: 将数组的第一个位置设为下边界: 将数组的最后一个位置设为上边界: 如果下边界等于或小于上边界,则做如下操作: 将中点设置为上边界加下边界之和除以二: 如果中点的元素小于查询的值,则将下边界设置为中点元素所在下标加1: 如果中点的元素大于查询的值,则将上边界设置为中点元素所在下标减1: 否则中点元素即为要查找的元素,可以进行
javascript折半查找详解

折半查找法: 在有序表中,把待查找数据值与查找范围的中间元素值进行比较,会有三种情况出现: 1) 待查找数据值与中间元素值正好相等,则放回中间元素值的索引. 2) 待查找数据值比中间元素值小,则以整个查找范围的前半部分作为新的查找范围,执行1),直到找到相等的值. 3) 待查找数据值比中间元素值大,则以整个查找范围的后半部分作为新的查找范围,执行1),直到找到相等的值 4) 如果最后找不到相等的值,则返回错误提示信息. 按照二叉树来理解:中间值为二叉树的根,前半部
C语言数据结构之折半查找实例详解

数据结构折半查找实例代码: /* 名称:折半查找语言:数据结构C语言版编译环境:VC++ 6.0 日期: 2014-3-26 */ #include <stdio.h> #include <malloc.h> #include <windows.h> #define N 11 // 数据元素个数 typedef int KeyType; // 设关键字域为整型 typedef struct // 数据元素类型 { KeyType key; // 关键字域 int
PHP实现的折半查找算法示例

本文实例讲述了PHP实现的折半查找算法.分享给大家供大家参考,具体如下: 定义:折半查找技术,也就是二分查找.它的前提是线性表中的记录必须是关键码有序(通常从大到小有序),线性表必须采用顺序存储. 折半查找的基本思想:取中间记录作为比较对象,若给定值与中间记录的关键字,则在中间记录的关键字相等,则查找成功:若给定值小于中间记录的作伴去继续查找:若给定值大于中间记录的关键字,则在中间记录的右半区继续查找.不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止. 实现代码: <?php

C++实现折半查找

相关推荐

随机推荐