和风细雨

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

二分法查找示例

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 和风细雨 阅读(382) 评论(0)  编辑  收藏 所属分类: 算法


只有注册用户登录后才能发表评论。


网站导航: