和风细雨

世上本无难事，心以为难，斯乃真难。苟不存一难之见于心，则运用之术自出。

二分法查找示例

package com.junglesong;

/**
 * 二分查找示例
 * @author: sitinspring(junglesong@gmail.com)
 * @date: 2008-3-8
 */
public class BinSearch{
    public static void main(String[] args){
        // 欲查找的数组
        int[] arr={1,2,3,4,5,6,77,88,656,5000,40000};
        
        // 测试数组
        int[] temp={4,5,6,77,88,656,1,2,400};        
        for(int i:temp){
            System.out.println("值"+i+"的下标为"+binSearch(arr,i));
        }
    }
    
    /**
     * 二分查找
     * @param sortedArray 已排序的欲查找的数组
     * @param seachValue 查找的值
     * @return 找到的元素下标，若找不到则返回-1
     */
    public static int binSearch(int[] sortedArray,int seachValue){
        // 左边界
        int leftBound=0;
        // 右边界
        int rightBound=sortedArray.length-1;
        // 当前下标位置
        int curr;
        
        while(true){
            // 定位在左边界和右边界中间
            curr=(leftBound+rightBound)/2;
            
            if(sortedArray[curr]==seachValue){
                // 找到值
                return curr;
            }
            else if(leftBound>rightBound){
                // 左边界大于右边界，已经找不到值
                return -1;
            }
            else{
                if(sortedArray[curr]<seachValue){
                    // 当当前下标对应的值小于查找的值时，缩短左边界
                    leftBound=curr+1;
                }
                else{
                    // 当当前下标对应的值大于查找的值时，缩短右边界
                    rightBound=curr-1;
                }
            }
        }
    }
}

代码下载：
http://www.blogjava.net/Files/junglesong/BinSearch20080308150836.rar

posted on 2008-03-08 14:26 和风细雨 阅读(391) 评论(0)  编辑  收藏 所属分类: 算法


只有注册用户登录后才能发表评论。
网站导航: