首页 > 学术百科

算法分析与设计-实验二二分查实验报告

南阳理工学院

算法分析与设计实验报告册

开课学院：计算机与软件学院

实验项目：实验2：二分查

实验时间：第6周周3（3,4）节

实验地点： 15#515

指导教师：

学生姓名：

学生学号：国家新农合信息平台

专业班级：

2020-2021学年第1学期

一、实验目的

1.掌握分治算法的基本设计思路、适用条件

2.非递归实现二分查

3.递归实现二分查

二、实验平台

1.JDK1.8

2.IDEA

三、实验内容

1.二分查：给定N个数据和待查的数据x，采用二分查算法来搜索x，输出x在N个数据中的位置。

四、算法设计

1.问题分析

根据问题需求可知，给定N个数据和待查的数据X，使用二分查算法来搜索x。要使用二分查算法，需要使数据有序，故可以将产生的数据进行排序（升序），之后取中间值记为data[mid]与x进行比较，如果x大于data[mid]则向数据的右侧再取mid进行比较

大连海事大学学报问题的终止条件为左指针>右指针

2.算法描述

二分查法（Binary Search）算法，也叫折半查算法。二分查针对的是一个有序的数据集合，查思想有点类似于分治思想。每次都通过跟区间的中间元素对比，将带查的区间缩小为之前的一半，知道到要查的元素，或者区间被缩小为0。二分查是一种非常非常高效的查询算法，时间复杂度为O(logn)。

3.算法求解步骤

第一步：对原数据data进行排序

第二步：设立左右指针left和right，左指针指向数组头部、右指针指向数组尾部

第三步：根据left和right计算出mid，并判断data[mid]与目标值target的大小

第四步：如果data[mid]大于target，则向右侧搜寻改变left指针值

第五步：如果data[mid]小于target，则向左搜寻改变right指针值

第六步：算法终止条件为到target元素或者left>right

四、算法源码

package experiment.binarysearch;

import java.util.Arrays;

import java.util.Random;

public class BinarySearch {

public static void main(String[] args) {

int[] data = getData(10);

System.out.println(Arrays.toString(data));

// binarySearch_NotRecursion(data,data[9]);

binarySearch_Recursion(data,data[3],0,data.length - 内含报酬率1);

}

// 生成待查数据有序

public static int[] getData(int length){

Random random = new Random();

int[] data = new int[length];

for(int i = 0;i<length;i++){

data[i] = Int(10*length);

}

Arrays.sort(data);

return data;

}

// 二分查非递归形式

public static void binarySearch_NotRecursion(int泥浆固液分离[] data,int target){

int left = 0;

int right = data.length - 1;

while(left <= right){

int mid = (left + right) / 2;

if (data[mid] == target){

System.out.println("查到需要的元素："+data[mid]+",在原数组中的下标为："+mid);

return;

}else if (data[mid] < target){

left = mid + 1;

戴高帽子的猫 }else if (data[mid] > target){

right = mid - 1;

}

System.out.println("未到需要搜索的元素");

}

// 二分查递归式

public static void binarySearch_Recursion(int[] data,int target,int left,int right){

if (left > right){

System.out.println("未到需要搜索的元素");

return;

}

int mid = (left + right) / 2;

if (data[mid] == target){

System.out.println("查到需要的元素："+data[mid]+",在原数组中的下标为："+mid);

return;

}else if (data[mid] < target){

left = mid + 1;

binarySearch_Recursion(data,target,left,right);

}else if (data[mid] > target){

right = mid - 1;

binarySearch_Recursion(data,target,left,right);

}复旦大学刘湘玲

}

本文发布于:2024-09-22 07:15:19，感谢您对本站的认可！

本文链接：https://www.17tex.com/xueshu/397692.html

上一篇：习题1.8二分查（20分）本题要求实现二分查算法。

下一篇：二分（二分答案、二分搜索）与单调性

标签：查找算法数据指针实验元素

留言与评论（共有 0 条评论）

算法分析与设计-实验二 二分查实验报告

算法分析与设计-实验二二分查实验报告