什么是二分查找？
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
二分查找优缺点
优点是比较次数少，查找速度快，平均性能好；
其缺点是要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
使用条件：查找序列是顺序结构，有序。
过程
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
利用循环的方式实现二分法查找
public class BinarySearch {
public static void main(String[] args) {
// 生成一个随机数组 int[] array = suiji();
// 对随机数组排序 Arrays.sort(array);
System.out.println("产生的随机数组为： " + Arrays.toString(array));
System.out.println("要进行查找的值： ");
Scanner input = new Scanner(System.in);
// 进行查找的目标值 int aim = input.nextInt();
// 使用二分法查找 int index = binarySearch(array, aim);
System.out.println("查找的值的索引位置： " + index);
}
/** * 生成一个随机数组 *
* @return 返回值，返回一个随机数组 */
private static int[] suiji() {
// random.nextInt(n)+m 返回m到m+n-1之间的随机数 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循环遍历为数组赋值 for (int i = 0; i < array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}
/** * 二分法查找 ---循环的方式实现 *
* @param array 要查找的数组 * @param aim 要查找的值 * @return 返回值，成功返回索引，失败返回-1 */
private static int binarySearch(int[] array, int aim) {
// 数组最小索引值 int left = 0;
// 数组最大索引值 int right = array.length - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
// 若查找数值比中间值小，则以整个查找范围的前半部分作为新的查找范围 if (aim < array[mid]) {
right = mid - 1;
// 若查找数值比中间值大，则以整个查找范围的后半部分作为新的查找范围 } else if (aim > array[mid]) {
left = mid + 1;
// 若查找数据与中间元素值正好相等，则放回中间元素值的索引 } else {
return mid;
}
}
return -1;
}}
运行结果演示：
由以上运行结果我们得知，如果要查找的数据在数组中存在，则输出该数据在数组中的索引；如果不存在则输出 -1 ，也就是打印 -1 则该数在数组中不存在，反之则存在。
四、利用递归的方式实现二分法查找
public class BinarySearch2 {
public static void main(String[] args) {
// 生成一个随机数组 int[] array = suiji();
// 对随机数组排序 Arrays.sort(array);
System.out.println("产生的随机数组为： " + Arrays.toString(array));
System.out.println("要进行查找的值： ");
Scanner input = new Scanner(System.in);
// 进行查找的目标值 int aim = input.nextInt();
// 使用二分法查找 int index = binarySearch(array, aim, 0, array.length - 1);
System.out.println("查找的值的索引位置： " + index);
}
/** * 生成一个随机数组 * * @return 返回值，返回一个随机数组 */
private static int[] suiji() {
// Random.nextInt(n)+m 返回m到m+n-1之间的随机数 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循环遍历为数组赋值 for (int i = 0; i < array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}
/** * 二分法查找 ---递归的方式 * * @param array 要查找的数组 * @param aim 要查找的值 * @param left 左边最小值 * @param right 右边最大值 * @return 返回值，成功返回索引，失败返回-1 */
private static int binarySearch(int[] array, int aim, int left, int right) {
if (aim < array[left] || aim > array[right]) {
return -1;
}
// 找中间值 int mid = (left + right) / 2;
if (array[mid] == aim) {
return mid;
} else if (array[mid] > aim) {
//如果中间值大于要找的值则从左边一半继续递归 return binarySearch(array, aim, left, mid - 1);
} else {
//如果中间值小于要找的值则从右边一半继续递归 return binarySearch(array, aim, mid + 1, array.length-1);
}
}}
运行结果演示：
总结：
递归相较于循环，代码比较简洁，但是时间和空间消耗比较大，效率低。在实际的学习与工作中，根据情况选择使用。通常我们如果使用循环实现代码只要不是太繁琐都选择循环的方式实现~
1.那些数可能无法得到S,也就是无解.如数组{6,7},数是9,那么无论怎么样都不会得到,而且初步看是个NP问题个人看法。
2.程序有错误,结果有问题!
3.除了static的和new出来的变量意外不需要考虑(new出来的东西可能出问题,static的一定出问题)
4.不知道算法是啥,,,,
5.没看明白要干啥
6.我觉得是4个.(f2,f3)算一个参数...而且传进去的是最后一个参数,也就是f3有效果(逗号表达式,最右边的有效)....崩溃了，平时还没见过这么写的....考试可真牛B
参考 http://zhidao.baidu.com/question/43079483.html?si=10
不懂
参考 http://zhidao.baidu.com/question/5884898.html?si=9
顶上面的
参考 http://zhidao.baidu.com/question/5913962.html?si=8
程序员考试大纲
一、考试说明
1. 考试要求：
(1) 熟练掌握DOS、WINDOWS95、WORD和上网软件的使用方法，以及有关基础知识；
(2) 掌握程序编制方法，用C语言编制简单程序；
(3) 掌握基本数据结构、程序语言和操作系统的基本知识；
(4) 了解数据库和信息安全的基础知识；
(5）掌握数制、机内代码和逻辑运算的基础知识；
(6)了解计算机主要部件和功能的基础知识；
(7) 了解多媒体和网络的基础知识；
(8) 理解计算机操作中常见的英语术语。
2. 通过本级考试的合格人员能熟练使用指定的常用软件和具有初步的程序编制能力，具有相当于技术员的实际工作能力和业务水平。
3. 本级考试范围包括: 基础知识（初级程序员级）, 考试时间为120分种；软件使用和程序编制初步能力，考试时间为120分钟。
二、考试范围
（一）基础知识
1.1软件基础知识
1．1．1基本数据结构
数组、纪录、列表、队列、栈（stack)的定义、存储和操作
1．1．2程序语言基础知识
汇编、编译、解释系统的基本概念和使用
程序语言的数据类型
程序语言的控制结构
1．1．3文件系统使用的基础知识
文件组织的类型和特点
文件操作命令的使用
1．1．4 操作系统的类型、功能和使用基础知识
1．1．5数据库系统基础知识
1．1．6多媒体基本概念
1．1．7上网浏览和收发电子邮件的基础知识
1．1．8计算机信息安全基础知识
计算机信息安全基本概念
常见计算机病毒的识别
1．2硬件基础知识
1．2．1数制及其转换
二进制、十进制和十六进制等常用数制及其相互转换
1．2．2机内代码
原码、补码、反码
定点数与浮点数的机内表示
ASCLL码级汉字编码等常用的编码
奇偶校验码
1．2．3逻辑运算
逻辑代数的基本运算和逻辑表达式的化简
1．2．4计算机的主要部件
中央处理器CPU、存储器和输入输出设备
1．2．5指令系统
常用的寻址方式
指令的格式分类及功能
1．2．6常用多媒体设备和网络通信设备的功能
1．3计算机专业英语
高中毕业英语程度
理解计算机操作中常见的英语术语
（二） 软件使用和程序编制初步能力
2.1 能熟练使用下列常用软件
2.1.1 操作系统（DOS和WINDOWS95）
2.1.2 字处理软件（WORD）
2.1.3 上网软件（电子邮件和浏览器）
2.2 能熟练使用下列程序语言编制程序
C（美国标准）
2.3 理解给定程序的功能
2.4 基本算法
查找、更新、排序和字符处理
2.5 程序编制方法
2.5.1 分支、循环、子程序（过程和函数）
2.5.2 输入输出和文件的基本处理
软件设计师考试大纲
一、 考试说明
1． 考试要求：
（1）掌握数据及其转换、数据的机内表示、算术和逻辑运算，以及相关的应用数学基础知识；
（2）理解计算机的组成以及各主要部件的性能指标；
（3）掌握操作系统、程序设计语言的基础知识；
（4）熟练掌握计算机常用办公软件的基本操作方法；
（5）熟练掌握基本数据结构和常用算法；
（6）熟练掌握C程序设计语言，以及C＋＋、Java、Visual Basic中的一种程序设计语言；
（7）熟悉数据库、网络和多媒体的基础知识；
（8）掌握软件工程的基础知识，了解软件过程基本知识、软件开发项目管理的常识；
（9）了解常用信息技术标准、安全性，以及有关法律、法规的基本知识；
（10）了解信息化、计算
package stack;
public class HalfSearch {
static int a[]={1,3,5,98,8,9,4,38,12};
public static int halfSeacrh(int[] a,int number){//二分查找
HalfSearch hs=new HalfSearch();
hs.bubbleSort(a);
int startPostion=0;
int endPostion=a.length-1;
int postion=(startPostion+endPostion)/2;
while(startPostion
return postion;
else if(a[postion]
}
else if(a[postion]>number){
endPostion=postion-1;
}
postion=startPostion+endPostion;
}
return -1;
}
public static void bubbleSort(int a[]){
int temp=0;
for(int i=0;i
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
}
public static void main(String[] args) {
System.out.println(halfSeacrh(a,8));
}
}
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024