二分法查找，二分法查找的原理是什么

本文目录一览

1，二分法查找的原理是什么
2，二分法查找
3，二分法查找的介绍
4，excel中lookup关于二分法
5，什么叫java中的二分查找法
6，C语言二分法查找问题

1，二分法查找的原理是什么

lbN,以2为底的对数，取上限，最多4次。原理是折半查找，每次把表分成两半，因为已经排序的，所以只需要和中间数比较就能确定是在哪一半，然后不断分成两半，直到匹配，或者没有数字，表示查找失败。次数最多就是上面提到的。

二分法查找的原理是什么

2，二分法查找

二分法查找又称折半查字法；思路是.恩!举例吧0，1，2，3，4，5，6，7，8中找5取数组中的一半也就是地五个4与5比较，如果4>5（就是中间的那个数比要找的那个大，那么就取那个数之前的那部分）；如果4<5（就是中间的那个数比要找的那个小，就取那个数只后的那部分）；如此循环下去；不好意思，语文没学好，表达不清楚

如果我没记错的话，二分查找的性能应该与二叉树类似~所以8个数（画出二叉图来）一共有1+2*2+3*4+4*1=21

二分法查找

3，二分法查找的介绍

算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。主要思想是：（设查找的数组区间为array[low, high]）（1）确定该期间的中间位置K（2）将查找的值T与array[k]比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。区域确定如下：a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……，K-1]b.array[k]<T 类似上面查找区间为array[k+1,……，high]。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间缩小一半。递归找，即可，时间复杂度:O(log2n)。

二分法查找的介绍

4，excel中lookup关于二分法

二分法查找算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。本例中2,8,4,5,6未排序，因此给出了末位的6；如果写成=LOOKUP(9,{2,4,5,6,8})，结果是8。

lookup认为数组中的值是以升序顺序放置的，在二分法下，它先中4开始查找（二分就是分成二部分，4在数组的中间,）当发现4<>9时，查找下一个5（因为是升序排序，所以它认为下一个数字比4大），5<>9时，查找6，当发现6<>9时且下面没数据可查找了。于是笨电脑就返回了这个 6，你如果把6改成大于9的数字，它就会返回5

5，什么叫java中的二分查找法

算法思想。　　①搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；　　②如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。　　③如果在某一步骤数组为空，则代表找不到。　　这种搜索算法每一次比较都使搜索范围缩小一半。

1、算法概念。　　二分查找算法也称为折半搜索、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。请注意这种算法是建立在有序数组基础上的。　　2、算法思想。　　①搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；　　②如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。　　③如果在某一步骤数组为空，则代表找不到。　　这种搜索算法每一次比较都使搜索范围缩小一半。　　3、实现思路。　　①找出位于数组中间的值，并存放在一个变量中（为了下面的说明，变量暂时命名为temp）；　　②需要找到的key和temp进行比较；　　③如果key值大于temp，则把数组中间位置作为下一次计算的起点；重复① ②。　　④如果key值小于temp，则把数组中间位置作为下一次计算的终点；重复① ② ③。　　⑤如果key值等于temp，则返回数组下标，完成查找。　　4、实现代码。/** * description : 二分查找。 * @param array 需要查找的有序数组 * @param from 起始下标 * @param to 终止下标 * @param key 需要查找的关键字 * @return */ public static > int binarySearch(E[] array, int from, int to, E key) throws Exception { if (from < 0 || to < 0) { throw new IllegalArgumentException("params from & length must larger than 0 ."); } if (from <= to) { int middle = (from >>> 1) + (to >>> 1); // 右移即除2 E temp = array[middle]; if (temp.compareTo(key) > 0) { to = middle - 1; } else if (temp.compareTo(key) < 0) { from = middle + 1; } else { return middle; } } return binarySearch(array, from, to, key); }

对于排序过的目标集合，然后每次都找中间的值，和目标值比大小，如果相等则结束，不然就到相应的半边继续这个步骤，直到找到目标为止因为每次找的范围都是上一次的一半，所以效率比直接查找快

string[] arr = arrays.sort(arr);//先排序(升序) system.out.println("排序后的结果:"+arrays.tostring(arr)); int index = arrays.binarysearch(arr, "java");//二分查找法"java" system.out.println(index);// 排序后的结果:[java, abd, hgd, java, red]// 0排序后,结果可能不是你想要的,可以数组直接转换成字符串,再利用indexof方法查找java在字符串中的位置

6，C语言二分法查找问题

#include<stdio.h>voidmain() floatx0,x1,x2,fx0,fx1,fx2; do printf("enterx1&x2:"); scanf("%f,%f",&x1,&x2); fx1=(x1*(2*x1-4)+3)*x1-6; fx2=(x2*(2*x2-4)+3)*x2-6; }while(fx1*fx2>0); /*如果f（x1），f（x2）同号，则在[x1,x2]区间无实根，重新输入x1，x2*/ do x0=(x1+x2)/2; /*求x1和x2间的中点：x0＝(x1＋x2)/2 */ fx0=(x0*(2*x0-4)+3)*x0-6; if((fx0*fx1)<0) x2=x0; fx2=fx0; } else x1=x0;fx1=fx0; } }while(fabs(fx0)>=1e-5);/*判断f（x0）的绝对值是否小于某一个指定的值（如10的负5次方）*/ printf("x=%6.3f\n",x0);/*输出x0*/ }

12345678910111213141516171819202122 #include<stdio.h>intmain() inta[10]= intn=7; intlow=0,high=10; intmid=0; while(low<=high) mid=(low+high)/2; if(n<a[mid]) high=mid-1; elseif(n>a[mid]) low=mid+1; else printf("%d",mid); break; //找到了，跳出循环就可以了 } } return0;}

#include <stdio.h>void main() float x0,x1,x2,fx0,fx1,fx2; do printf("enter x1 & x2:"); scanf("%f,%f",&x1,&x2); fx1=(x1*(2*x1-4)+3)*x1-6; fx2=(x2*(2*x2-4)+3)*x2-6; }while(fx1*fx2>0); /*如果f（x1），f（x2）同号，则在[x1,x2]区间无实根，重新输入x1，x2 */ do x0=(x1+x2)/2; /*求x1和x2间的中点：x0＝(x1＋x2)/2 */ fx0=(x0*(2*x0-4)+3)*x0-6; if((fx0*fx1)<0) x2=x0; fx2=fx0; } else x1=x0; fx1=fx0; } }while(fabs(fx0)>=1e-5);/*判断f（x0）的绝对值是否小于某一个指定的值（如10的负5次方）*/ printf("x=%6.3f\n",x0); /*输出x0*/ }

a.txt: 读入数据b.txt: 写入排序数据c.txt: 写入查找结果#include <stdio.h>const int maxn = 1000;int num[maxn], n;void swap(int* x,int* y) { *x ^= *y; *y = *x^*y; *x = *x^*y;}void finput() { printf("--------\nread data from a.txt\n--------\n\n"); FILE* fin = fopen("a.txt","r"); n = 0; while ( fscanf(fin,"%d",&num[n]) != EOF ) { n++; } fclose(fin);}void bubble() { printf("--------\nstart bubbling sort algorithm\n"); for (int i = n-1; i > 0; --i) { for (int j = 0; j < i; ++j) { if (num[j] > num[j+1]) { swap(&num[j],&num[j+1]); } } } printf("write the result of sort in b.txt\n--------\n\n"); FILE* fout = fopen("b.txt","w"); for (int i = 0; i < n; ++i) { fprintf(fout,"%d\n", num[i]); } fclose(fout);}int rbesearch(int low,int high,int v) { // recursive binary search // return the index of v. if not exists, return -1. if (low == high) { if (num[low] == v) return low; return -1; } if (num[low] == v) return low; int mid = (low+high)/2; if (num[mid] < v) { return rbesearch(mid+1,high,v); } else { return rbesearch(low,mid,v); }}int nrbesearch(int low,int high,int v) { // non-recursive binary search // return the index of v. if not exists, return -1. while (low < high) { int mid = (low+high)/2; if (num[mid] < v) { low = mid+1; } else { high = mid; } } if (low == high && num[low] == v) { return low; } return -1;}void search() { printf("--------\n"); printf("Start search.\n"); printf("The results will be written in c.txt\n"); printf("please input a num. if num = -123456, quit.\n"); FILE* file=fopen("c.txt","w"); while (true) { int v; scanf("%d", &v); if (v == -123456) break; int rb = rbesearch(0,n-1,v); int nrb = nrbesearch(0,n-1,v); fprintf(file,"input: %d\n",v); fprintf(file,"the result of recursive binary search: %d\n", rb); fprintf(file,"the result of non-recursive binary search: %d\n\n", nrb); printf("the result of recursive binary search: %d\n", rb); printf("the result of non-recursive binary search: %d\n\n",nrb); } fclose(file); }int main() { finput(); bubble(); search(); return 0;}