二分搜索技术

题目：给定排好序的n个元素a[0:n-1], 现在在这n个元素中找到一特定的元素x

分析：

分析一下，如果用顺序搜索法来找到这个数，那么需要O（n）次比较

比较浪费给定的条件——已经是排好顺序了,所以换一种思想

利用二分搜索法，即分治的思想，分成k个子问题:每次减一半，缩小范围

看代码：比较简洁

package hello;
import java.util.*;

public class M1 {

    public static void main(String[] args) {
    int a[]=new int[] {1,2,3,4,5};
    int result=binarySearch(a, 2, 5);
    System.out.println("要找的数的位置在数组下标为"+result+"的位置");
      
    }
    //给定的数组已经排好顺序了
    public static int binarySearch(int a[],int x,int n) {
    	//分析一下，如果用顺序搜索法来找到这个数，那么需要O（n）次比较
    	//，比较浪费给定的条件——已经是排好顺序了,所以换一种思想
    	//利用二分搜索法，即分治的思想，分成k个子问题:每次减一半，缩小范围
    	int left=0;
    	int right=n-1;
    	while(left<=right) {
    		int middle=(left+right)/2;
    		if(x==a[middle]) return middle;
    		if(x>a[middle]) left=middle+1;
    		else right=middle-1;
    	}
    	return -1;
    }
}