折半查找 

给定一组数据，先进行快速排序，再进行折半查找

import java.util.*;
/**
 * @version 1.0
 * @author zhouxiaowu
 *
 */
public class BinSearch {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println("please input dataset:");
        String str = sc.nextLine();
        String[] s = str.split("\\s+");
        System.out.println("please input search value:");
        int value = sc.nextInt();
        int[] nums = new int[s.length];
        for(int i=0;i<nums.length;i++){
            nums[i]=Integer.parseInt(s[i]);
        }
        Qsort(nums,0,nums.length-1);
        System.out.println("sorted dataset:");
        for(int i:nums)
            System.out.print(i+" ");
        System.out.print("\n");
        int result = binSearch(nums,value);
        System.out.println(value+":"+result);
    }
    public static void Qsort(int[] num,int low,int high){
        if(low<high){
            int part = partition(num,low,high);
            if(low<part-1) Qsort(num,low,part-1);
            if(high>part+1) Qsort(num,part+1,high);
        }

    }
    public static int partition(int[] num,int p,int q){
        int low =p,high=q;
        int temp =num[low];
        while(low<high){
            while(low<high&&temp<=num[high])
                high--;
            if(low<high)
                num[low++]=num[high];
            while(low<high&&temp>=num[low])
                low++;
            if(low<high)
                num[high--]=num[low];
        }
        num[low]=temp;
        return low;

    }
    public static int binSearch(int[] num,int value){
        int low = 0;
        int high = num.length-1;
        int mid;
        while(low<=high){
            mid=(low+high)/2;
            if(num[mid]==value) 
                return mid;
            else if(num[mid]>value)
                high=mid-1;
            else 
                low = mid+1;
        }
        return -1;

    }

}


测试结果： 

Input：please input dataset: 

                15 7 9 2 12 8 1 

            please input search value: 

                9 

output：sorted dataset: 

                1 2 7 8 9 12 15  

                9:4

折半查找（二分查找）
用的是二分法，即待查元素与表中间位置比较，相等则查找成功，否则将表分成前后两个子表，
如果中间位置记录大于待查元素 ，则进一步去查找前表，否则查找后一表 。


使用折半查找有两个要求：1，必须采用顺序存储结构；2，必须按关键字大小有序排列


上代码：
public class 二分查找 {
	/**
	 * 
	 * @return key所在索引值
	 */
	public int search(int key, int data[]) {
		int start = 0, end = data.length - 1;
		while (start <= end) {
			int mid = (start + end) / 2;
			if (key == data[mid]) {
				return mid;
			} else if (key > data[mid]) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		return -1;

	}

	public static void main(String[] args) {
		int[] data = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

		Scanner in = new Scanner(System.in);
		int key = in.nextInt();
		int index = new 二分查找().search(key, data);
		if (index == -1) {
			System.out.println("CAN NOT FIND IT");
		} else {
			System.out.println("索引是：" + index);
		}
	}

}

/*
折半查找
*/
class TwoSearch
{
//折半查找可以提高效率，但必须得保证是有序的数组
public static int halfSearch(int[] arr,int key)//折半查找函数
{
int min,max,mid;
min=0;
max=arr.length-1;
mid=(min+max)/2;
while(arr[mid]!=key)
{
if(key>arr[mid])
{
min=mid+1;
}else if(key
{
max=mid-1;
}
if(min>max)           //如果数组中没有所求的数，返回-1
return -1;
mid=(min+max)/2;     //保证函数继续
}
return mid;
}
public static void main(String[] args) //主函数
{
int[] arr={6,13,25,33,56,67,89,99,123,387};//必须定义有序的数组
int key=halfSearch(arr,89);
System.out.println("key= "+key);
}
}
作者：qiuxuewei2012 发表于2013-7-20 12:47:22   原文链接
阅读：15 评论：0   查看评论

package shujujiegou;

public class binarySearch {
	public int go(int[] array,int m){
		int begin_p=0;
		int end_p=array.length-1;//因为index要比数组长度小1
		while(begin_p<=end_p){//这里如果没找到会break，比用true好！
			int half=(begin_p+end_p)/2;//定义在这里，会自动每次循环前赋值，不用在if里面赋值
			if(m>array[half]){
				begin_p=half+1;//在这里加1，能减少计算
			}else if(m<array[half]){
				end_p=half-1;//在这里减1，能减少计算
			}else{
				return half;
			}
		}
		return -1;
	}
	public static void main(String[] args){
		binarySearch bs=new binarySearch();
		int[] array={1,2,3,4,5,6,7,8,9,10};//Arrays.sort(array)能返回排序号的array,不过要import java.util.*;
		System.out.println(bs.go(array,8));
	}
}
折半查找，最多只要logN次查找。比如2最多能折1次，4最多只能折2次。