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);
 cout<<"Please input 15 numbers:"<<endl;
 for(i=0;i<15;i++){
  cin>>a[i];
 }
 cout<<"Sorted order:"<<endl;
 //==============选择排序========
 array_sort(a,15);
 //=======输出排序完成的数组====
    for(i=0;i<15;i++){
  cout<<a[i]<<" ";
  }
 cout<<endl;
 cout<<"please input a number:";
 cin>>n;
 //================折半查找==========
 cout<<endl;
 cout<<"number "<<n<<" locate in "<<zeban(a,0,14,n)<<endl;
 return 0;
}
void array_sort(int a[],int n){
 int i,j,k,tool;
     for(i=0;i<n;i++){
  k=i;
  for(j=(i+1);j<n;j++){
  if(a[j]<a[k]){
     k=j;
        }
  }
  tool=a[i];
  a[i]=a[k];
  a[k]=tool;
  }
}
int zeban(int a[],int start,int end,int n){
 int tag=-1;
 for(start=0,end=14;start<=end;){
  if(n==a[(start+end)/2]){
   tag=(start+end)/2+1;
   return tag;
  }else if(n<a[(start+end)/2]){
   end=(start+end)/2;
  }else if(n>a[(start+end)/2]){
   start=(start+end)/2;
  }
 }
}

第二种方法:

冒泡排序法+递归折半查找法


代码如下:

#include<iostream>
using namespace std;
int main(){
 int a[15];
 int n,i;
 void array_sort(int a[], int n);
    int IterBiSearch(int data[], const int x, int beg, int last);
 cout<<"Please input 15 numbers:"<<endl;
 for(i=0;i<15;i++){
  cin>>a[i];
 }
 cout<<"Sorted order:"<<endl;
 //==============选择排序========
 array_sort(a,15);
 //=======输出排序完成的数组====
    for(i=0;i<15;i++){
  cout<<a[i]<<" ";
  }
 cout<<endl;
 cout<<"please input a number:";
 cin>>n;
 //================折半查找==========
 cout<<endl;
 cout<<"number "<<n<<" locate in "<<IterBiSearch(a,n, 0, 14)<<endl;
 return 0;
}
void array_sort(int a[],int n){
 int i,j,tool;
     for(i=0;i<n;i++){
     for(j=0;j<(n-i-1);j++){
        if(a[j]>a[j+1]){
           tool=a[j];
           a[j]=a[j+1];
           a[j+1]=tool;
        }
     }
    }
}
int IterBiSearch(int data[], const int x, int beg, int last) 

    int mid = -1; 
    mid = (beg + last) / 2; 
    if (x == data[mid]) 
    { 
        return (mid+1); 
    } 
    else if (x < data[mid]) 
    { 
        return IterBiSearch(data, x, beg, mid - 1); 
    } 
    else if (x > data[mid]) 
    { 
        return IterBiSearch(data, x, mid + 1, last); 
    } 
    return -1; 
}

(0)

相关推荐

  • C++快速排序的分析与优化详解

    相信学过数据结构与算法的朋友对于快速排序应该并不陌生,本文就以实例讲述了C++快速排序的分析与优化,对于C++算法的设计有很好的借鉴价值.具体分析如下: 一.快速排序的介绍 快速排序是一种排序算法,对包含n个数的输入数组,最坏的情况运行时间为Θ(n2)[Θ 读作theta].虽然这个最坏情况的运行时间比较差,但快速排序通常是用于排序的最佳的实用选择.这是因为其平均情况下的性能相当好:期望的运行时间为 Θ(nlgn),且Θ(nlgn)记号中隐含的常数因子很小.另外,它还能够进行就地排序,在虚拟内存

  • c++快速排序详解

    说一说快速排序 快速排序,实际中最常用的一种排序算法,速度快,效率高,在N*logN的同等级算法中效率名列前茅.· 基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分所有数据要小,然后再按此方法对这两部分数据分别进行快速排序.整个排序过程可以递归进行,以此达到整个数据变成有序序列. 将数列变成上述形式,这一步很关键,做好这一步,才能对主元左右的部分进行递归调用.以下是实现这一部分的代码: int partition_sort(int arr[],int l

  • c++实现对输入数组进行快速排序的示例(推荐)

    废话不多说,直接上代码 #include "stdafx.h" #include <iostream> #include <string> #include <vector> using namespace std; void quickSort(vector<int> &a, int, int); void swap(int &a, int&b); vector<string> split(strin

  • C/C++实现快速排序的方法

    快速排序不会直接得到最终结果,只会把比k大和比k小的数分到k的两边.(你可以想象一下i和j是两个机器人,数据就是大小不一的石头,先取走i前面的石头留出回旋的空间,然后他们轮流分别挑选比k大和比k小的石头扔给对面,最后在他们中间把取走的那块石头放回去,于是比这块石头大的全扔给了j那一边,小的全扔给了i那一边.只是这次运气好,扔完一次刚好排整齐.)为了得到最后结果,需要再次对下标2两边的数组分别执行此步骤,然后再分解数组,直到数组不能再分解为止(只有一个数据),才能得到正确结果. -- 取自百度百科

  • 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

  • PHP有序表查找之二分查找(折半查找)算法示例

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

  • 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时,说明目标关键字在整个有序

  • C++二分查找(折半查找)算法实例详解

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

  • 基于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

随机推荐