折半查找算法及代码？

一、折半查找算法及代码？

#include<iostream>

#define MAX_SIZE 102

using namespace std;

template <class T>

int BinarySearch(T a[],const T&x,int n,int left,int right)

{

if(left>=right)

return -1;

else

{

if(a[(left+right)/2]==x)

return (left+right)/2;

else if(x>=(left+right)/2)

return BinarySearch(a,x,n,(left+right)/2+1,right);

else if(x<(left+right)/2)

return BinarySearch(a,x,n,left,(left+right)/2-1);

}

}

int main()

{

int a[MAX_SIZE];

int i,len,x,p;

cin>>len;

for(i=0;i<len;i++)

cin>>a[i];

cin>>x;

p=BinarySearch(a,x,len,0,len-1);

if(p==-1)

cout<<"该数不存在！"<<endl;

else

cout<<p+1<<endl;

return 0;

}

二、折半查找的适用条件？

适用的前提条件：

1. 存储在数组中（例如一维数组）

2. 数组元素为有序（例如升序）查找的基本思想：折半查找，设查找的元素为value value与中间元素（middle = left + (right -left) / 2这样做的好处防止中间元素出现越界）比较，若比中间值小则查找范围在middle + 1继续查找，若比中间值大则查找范围在middle -1,若与中间值相等则查找结束索引元素为value = middle。

三、折半查找算法实验心得？

二分查找法要从时间复杂度，空间复杂度等进行实验分析

四、折半查找法例题分析？

package com.aozhi.test;

public class BinarySearch {

/*

* 循环实现二分查找算法arr[] 已排好序的数组x

* return 返回索引下标

*/

public static int binarySearch(int[] arr, int x) {

int low = 0;

int high = arr.length - 1;

while (low <= high) {//判断非空

int middle = (low + high) / 2;//折半从中间开始

if (x == arr[middle]) {//是中间的直接返回

return middle;

} else if (x < arr[middle]) {//因为他是有序的数组，可以根据中间值作比较

high = middle - 1;

} else {

low = middle + 1;

}

}

return -1;

}

public static void main(String[] args) {

int[] arr = { 6, 12, 33, 87, 90, 97, 108, 561 };

System.out.println("循环查找：" + (binarySearch(arr, 6)));

}

}

五、折半查找法怎么找？

①折半查找法是效率较高的一种查找方法。

②折半查找法怎么找？

答：假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是：设查找数据的范围下限为l=1，上限为h=5，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；如此重复前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。

六、顺序查找和折半查找的算法心得？

1.顺序查找:<适合对象——无序或有序队列>

思想:逐个比较,直到找到或者查找失败。

时间复杂度:T(n) = O(n)。

2.折半查找:<适合对象——只是适用于有序表,且限于顺序存储结构(线性链表无法进行折半查找)>

思想:又称二分查找,对于已经按照一定顺序排列好的列表,每次都用关键字和中间的元素...

时间复杂度:T(n) =O(logn)。

七、折半查找递归算法如何实现？

在计算机科学中，折半搜索(英语:haⅠfinτerα|search)，也称二分搜索(英语:bⅰnarysearch)，对数搜索(英语:|ogarⅰthmⅰcseαrch)，是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从数组的中间元素开始，如果中问元素正好是要查找的元素，则搜索过程结束。如果某一特定元素大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

八、关于折半查找的比较次数？

第五个查找1次 第二个和第七个查找两次 第一，第三和第六，第八要查找三次 第四和第九要查找四次 一共25次 ASL=25/9 查找值为21的结点，需要比较2次。

九、如何求折半查找的比较次数？

解： 先把它写成完全二叉树的形式：每次都从根结点开始，查找一次成功的有1个结点，二次有2个，三次有4个，四次有5个。 所以平均幽会数次数=（1*1+2*2+3*4+4*5）/12=37/12。

十、二分查找和折半查找一样吗？

二分查找算法是一种快速的查找算法。当我们再一个数组中查找是否存在某个数时，通常是直接遍历这个数组直到找到这个数，时间复杂度为O(n)试想如果数据量很大,这里可以用一种简单快速的的查找算法--二分查找算法，也叫做折半查找算法。

顶一下

(0)

0%

踩一下

(0)

0%