二分查找效率（学会二分查找）
二分查找效率（学会二分查找）有人可能会问了，要是查找的数在第一个，那二分查找法的效率就比不上遍历法了。确实，查找的数在第一个的话，那么遍历只要找一次就够了，但是在实际应用时，绝大多数情况还是要查找位于中间的数，在首位的情况只是特例。这时我们发现Array[mid]=x=17，仅仅只是查找了两次就找到了这道菜，如果用从头到尾遍历的方法，需要找五次，而且随着元素数量的增加，二分查找的高效率会反映的更明显。怎么做二分查找呢面对有序的n个数时，要在其中查找出一个数x时，最容易想到的办法是从头到尾遍历，遇到值为x的则输出。如果要查找的x在第一位，马上就可以查找出来；但要查找的x在最后一位，那就需要遍历全部n个数。有没有效率更高的算法呢？当然有，这就是二分查找。首先我们要利用n个数有序的这个性质，假定顺序为升序，并存放在数组Array[]中。取这一组数的查找范围的上边界为low，初值为low=0；查找范围的下边界为high，初值
我们走进了一家餐厅，找了空桌子坐下，服务员过来递给我们一本菜单。
枇伊：“这家餐厅有一道菜价格17元，特别好吃，你帮我找一找吧。”
我刚要翻开菜单，她马上叫住了我，说到：“这家餐厅的菜单有一个特点，每页有一道菜，价格是递增的，后一页菜的价格一定比前一页贵，每页侧面都有一个突出的标签标明了页数，你试试能不能尽快的找出那道菜。”
我：“没问题交给我吧。(这人好无聊啊，吃个饭还要考我一下二分查找)”。
怎么做二分查找呢
一.基本思想
面对有序的n个数时，要在其中查找出一个数x时，最容易想到的办法是从头到尾遍历，遇到值为x的则输出。如果要查找的x在第一位，马上就可以查找出来；但要查找的x在最后一位，那就需要遍历全部n个数。有没有效率更高的算法呢？当然有，这就是二分查找。首先我们要利用n个数有序的这个性质，假定顺序为升序，并存放在数组Array[]中。取这一组数的查找范围的上边界为low，初值为low=0；查找范围的下边界为high，初值为high=n-1；中间数下标mid=(low high)/2，若Array[mid]=x，则可以直接输出或返回。若Array[mid]>x，依据升序的原则可以判断出x在前半部分，令high=mid-1。若Array[mid]<x，依据升序的原则可以判断出x在后半部分，令low=mid 1。之后在前半部分或后半部分继续用该思想查找，直到找到目标数。
以故事中的菜单为例，把菜单中各道菜的价格按序放到数组中，查找范围的上边界为low，下边界为high。每次查找的中间值下标为mid，查找的数x=17。
- 第一次查找
- 第二次查找
这时我们发现Array[mid]=x=17，仅仅只是查找了两次就找到了这道菜，如果用从头到尾遍历的方法，需要找五次，而且随着元素数量的增加，二分查找的高效率会反映的更明显。
有人可能会问了，要是查找的数在第一个，那二分查找法的效率就比不上遍历法了。确实，查找的数在第一个的话，那么遍历只要找一次就够了，但是在实际应用时，绝大多数情况还是要查找位于中间的数，在首位的情况只是特例。
当然，这种算法也有不足之处。它只能对有序数列进行查找，对无序数列不能使用这种算法。
二.代码二分查找有两种实现形式：递归形式和非递归形式。
用两种语言表示程序，递归程序使用C ，非递归程序使用java
递归形式
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int binarysearch(int Array[] int x int low int high)
{
if (low > high)return -1;//Returns -1 if the element is not found
int mid = (low high)/2;
if (Array[mid] == x)//Find the element
{
return mid;//return
}
else if (Array[mid] > x)//The number found is greater than the target
{
return binarysearch(Array x low mid - 1);//Look for the first half
}
else//The number found is less than the target
{
return binarysearch(Array x mid 1 high);//Look for the second half
}
}
int main()
{
int Array[1000];
int n x;
scanf("%d" &n);
for (int i = 0;i < n;i )
scanf("%d" &Array[i]);
scanf("%d" &x);
sort(Array Array n);
int flag = binarysearch(Array x 0 n - 1);
if (flag == -1)printf("此数不存在\n");
else printf("此数排序后在第%d个位置" flag 1);
return 0;
}
非递归形式
import java.util.Arrays;
import java.util.Scanner;
public class Search {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] Array1=new int[n];
for(int i=0;i<n;i ){
Array1[i]=sc.nextInt();
}
Arrays.sort(Array1);
int x=sc.nextInt();
int flag=binarysearch(Array1 x 0 n-1);
if(flag==-1){
System.out.println("此数不存在");
}else{
System.out.printf("此数排序后在第%d个位置" flag 1);
}
}
private static int binarysearch(int[] Array1 int x int low int high){
while(low<=high){
int mid=(low high)/2;
if(Array1[mid]==x){//Find the element
return mid;//return
}else if(Array1[mid]>x){//The number found is greater than the target
high=mid-1;//Look for the first half
}else{//The number found is less than the target
low=mid 1;//Look for the second half
}
}
return -1;//Returns -1 if the element is not found
}
}
此号从这篇文章开始正式更名为【堆栈树图】(这个名字感觉更接近发布文章的主题)，公众号也改成此名，如果发布的文章对您有所帮助，欢迎关注公众号--【堆栈树图】，阅读更多类似文章。如果文章中有不足之处，也欢迎批评指正。
