二分搜索

3.二分查找（Binary Search）——在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。

Technique for finding a particular value in a linear array, by ruling out halfof the data at each step.

二分查找是也称作折半查找，是一种效率较高的查找，但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找图

程序代码如下:

package thirty_two.A_Search;

import java.util.Scanner;

/**

* 二分查找

* @author 

* 给定一个有序的数组，实用二分查找寻找数字P是否存在数组中

*

*/

public class BinarySearch {

            public static void main(String[] args) {

                    Scanner in=new Scanner(System.in); 

                     System.out.println("请输入数组的长度N");

                     int n=in.nextInt();

                      int[] array=new int[n];

                      System.out.println("请输入长度为"+n+"的整型数组:");

                    for(int i=0;i<n;i++) {

                                array[i]=in.nextInt();

                        }

                    System.out.println("请输入需要寻找的数字P:");

                    int P=in.nextInt();

                    System.out.println(binarySearch(array,P,0,array.length-1));

}

public static boolean binarySearch(int[] array,int P,int head,int tail) {

                while(head<=tail) {

                        int mid=(tail+head)/2;

                        if(tail-head<=1) {

                        if(array[head]==P) {

                                System.out.println("index="+head);

                                return true;

                        }else if(array[tail]==P){

                                 System.out.println("index="+head);

                                return true;

                        }else {

                                return false;

                        }

        }

        if(array[mid]==P) {

                System.out.println("index="+mid);

                return true;

        }

        if(array[mid]>P) {

                tail=mid;

        }

        if(array[mid]<P) {

                head=mid;

        }

    }

return false;

}

}