7.16（执行时间）编写程序，随机产生一个包含100 000个整数的数组和一个关键字。估算调用程序清单7-6中的linearSearch方法的执行时间

• 题目
• • 题目描述
  • 程序清单7-6的linearSearch
  • 程序清单7-7BinarySearch
  • 破题
• 代码
• • 运行实例

题目

题目描述

7.16（执行时间）编写程序，随机产生一个包含100 000个整数的数组和一个关键字。估算调用程序清单7-6中的linearSearch方法的执行时间。对该数组进行排序，然后估算调用程序清单7-7中的binarySearch方法的执行时间。可以使用下面的代码模板获取执行时间

long startTime = System.nanoTime();
perform the task;			// 在这里调用方法
long endTime = System.nanoTime();
long executionTime = endTime - startTime;

程序清单7-6的linearSearch

public class LinearSearch{public static int linearSearch(int[] list, int key){for (int i = 0 ; i < list.length; i++){if (key == list[i])return i;}return -1;}
}

程序清单7-7BinarySearch

public class BinarySearch{
public static int binarySearch(int[] list, int key){int low = 0;int high = list.length - 1;while(high >= low){int mid = (low + high) / 2;if (key < list[mid])high = mid - 1;else if (key == list[mid])return mid;elselow = mid + 1;}return -low-1;}
}

破题

1. 主方法：随机生成100 000个整数，存入数组中
2. 主方法：从这100 000个整数中随机生成一个key（可以生成下标，再从数组中抽出）
3. 主方法：调用方法linearSearch并估算时间
4. 主方法： 对数组进行排序
5. 主方法：调用binarySearch方法并估算时间

代码

import java.util.Arrays;public class Test7_16 {public static void main(String[] args) {//1. 主方法：随机生成100 000个整数，存入数组中int[] list = new int[100000];for (int i = 0; i < 100000; i++){list[i] = (int)(Math.random() * 100000);}//2. 主方法：从这100 000个整数中随机生成一个key（可以生成下标，再从数组中抽出）int key_index = (int) (Math.random() * 100000);int key = list[key_index];//3. 主方法：调用方法linearSearch并估算时间（，输出）long startTime0 = System.nanoTime();linearSearch(list, key);        // 4.long endTime0 = System.nanoTime();long executionTime0 = endTime0 - startTime0;System.out.println(executionTime0);//5. 主方法： 对数组进行排序Arrays.sort(list);//6. 主方法：调用binarySearch方法并估算时间long startTime1 = System.nanoTime();binarySearch(list, key);long endTime1 = System.nanoTime();long executionTime1 = endTime1 - startTime1;System.out.println(executionTime1);}// 线性查找法public static int linearSearch(int[] list, int key){for (int i = 0 ; i < list.length; i++){if (key == list[i])return i;}return -1;}// 二分查找法public static int binarySearch(int[] list, int key){int low = 0;int high = list.length - 1;while(high >= low){int mid = (low + high) / 2;if (key < list[mid])high = mid - 1;else if (key == list[mid])return mid;elselow = mid + 1;}return -low-1;}
}

运行实例

213333
12337

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！