本文目录
二分法是什么意思
二分法是数学领域术语。
二分法即，对于区间上连续不断且f（a）·f（b）《0的函数y=f（x），通过不断地把函数f（x）的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫二分法。
算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。
基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，
如果当前位置arr值等于key，则查找成功；
若key小于当前位置值arr；
若key大于当前位置值arr，
直到找到为止，时间复杂度:O(log(n))。
C++语言中的二分查找法：
基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。
假如有一组数为3，12，24，36，55，68，75，88要查给定的值24.可设三个变量front，mid，end分别指向数据的上界，中间和下界，mid=（front+end）/2。
1、开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为mid》x，故应在前半段中查找。
2、令新的end=mid-1=2，而front=0不变，则新的mid=1。此时x》mid，故确定应在后半段中查找。
3、令新的front=mid+1=2，而end=2不变，则新的mid=2，此时a=x，查找成功。
如果要查找的数不是数列中的数，例如x=25，当第三次判断时，x》a，按以上规律，令front=mid+1，即front=3，出现front》end的情况，表示查找不成功。
二分查找算法
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。 int binSearch(const int *Array,int start,int end,int key){int left,right;int mid;left=start;right=end;while (left《=right) { /注释中为递归算法，执行效率低，不推荐mid=(left+right)/2;/* if (key《Array){left=mid+1;}elsereturn mid;}return -1;}
对分查找和二分查找 有什么区别
一般都称为二分查找，二分查找也称折半查找（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) {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 》 aim) {//如果中间值大于要找的值则从左边一半继续递归 return binarySearch(array, aim, left, mid - 1);} else {//如果中间值小于要找的值则从右边一半继续递归 return binarySearch(array, aim, mid + 1, array.length-1);}}}运行结果演示：
总结：
递归相较于循环，代码比较简洁，但是时间和空间消耗比较大，效率低。在实际的学习与工作中，根据情况选择使用。通常我们如果使用循环实现代码只要不是太繁琐都选择循环的方式实现~
对比顺序查找,二分查找和哈希查找算法,它们各自的特点是什么
顺序查找,二分查找和哈希查找算法,它们各自的特点是：1.对比顺序查找的特点就是从表的第一个元素开始一个一个向下查找，如果有和目标一致的元素，查找成功;如果到最后一个元素仍没有目标元素，则查找失败。2.二分查找的特点就是从表中间开始查找目标元素。如果找到一致元素，则查找成功。如果中间元素比目标元素小，则仍用二分查找方法查找表的后半部分(表是递增排列的)，反之中间元素比目标元素大，则查找表的前半部分。3.哈希算法的特点是是使用给定数据构造哈希表，然后在哈希表上进行查找的一种算法。先给定一个值，然后根据哈希函数求得哈希地址，再根据哈希地址查找到要找的元素。是通过数据元素的存储地址进行查找的一种算法。
二分法查找的适用条件
说”二分查找法只适用于顺序存储的有序表“是正确的，说”指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）“是为了程序的确定性。 实际上只要有序就可以。按递减排序也可以用二分法。只是必须把算法规则改变一下。 递增的算法：拿要查找数值与中间序号的数值比较若相等，查找成功；要查找数值比中间序号的数值大，在右边查找，低端序号改为原中间序号加1；要查找数值比中间序号的数值小，在左边查找，高端序号改为原中间序号减1；如此反复。 递减的算法：拿要查找数值与中间序号的数值比较若相等，查找成功；要查找数值比中间序号的数值大，在左边查找，高端序号改为原中间序号减1；要查找数值比中间序号的数值小，在右边查找，低端序号改为原中间序号加1；如此反复。
求二分查找基本思想~
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。二分查找,别称折半查找Binary-Search优点:查找速度快条件:待查表为有序表1算法要求:必须采用顺序存储结构2.必须按关键字大小有序排列。算法复杂度:假设其数组长度为n，其算法复杂度为o（log（n））下面提供一段二分查找实现的伪代码:BinarySearch(max,min,des)mid-《(max+min)/2while(min《=max)mid=(min+max)/2if mid=des thenreturn midelseif mid 》des thenmax=mid-1elsemin=mid+1return max折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a，则我们只要在数组a的右 半部继续搜索x。
二分查找法
总共13个，从0开始，最大是12，使用二分法原则分析如下第一次：12/2=6 , (6)=45《90第二次:(7+12)/2=9,(9)=77《90第三次:(10+12)/2=11,(11)=95》90第四次:((11-1)+10)/2=10,(10)=90 查找成功
什么是二分查找〉
二分查找也称折半查找（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) {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 》 aim) {//如果中间值大于要找的值则从左边一半继续递归 return binarySearch(array, aim, left, mid - 1);} else {//如果中间值小于要找的值则从右边一半继续递归 return binarySearch(array, aim, mid + 1, array.length-1);}}}运行结果演示：
总结：
递归相较于循环，代码比较简洁，但是时间和空间消耗比较大，效率低。在实际的学习与工作中，根据情况选择使用。通常我们如果使用循环实现代码只要不是太繁琐都选择循环的方式实现~
