Java 二分查找的实现

我就是我 2023-02-23 01:30 9阅读 0赞

# 二分查找： #

二分查找的前提对数组是有要求的。数组必须已经排好序。  
每次先与中间的元素进行比较。如果大于往右边找。如果小于往左边找，如果等于就返回该元素索引位置  
如果没有该元素，返网-1。综合性能比较好:↑

# 实现方法： #

1.  定义一个方法。记录开始的索引位置和结束的索引位置。
2.  取出中间索引位置的值，拿元素与中间位置的值进行比较。  
    如果小于中间值，结束位置=中间索引-1。
3.  取出中间素引位置的值，拿元素与中间位置的值进行比较。  
    如果大于中间值，开始位置=中间索引+1。

循环正常执行的条件是：  
开始位置索引<=结束位置索引。  
否则说明寻找完毕但是还是没有该元素值，返回-1。

/** * 二分查找的算法实现 * 如果元素存在返回索引值 * 如果元素不存在返回-1 */
    
    public class 二分查找 { 
        public static void main(String[] args) { 
    
            int[] arr = { 12,22,35,48,55,68,72,89};
            int rs = binarySearch(arr, 55);
            System.out.println(rs);
        }
    
        public static int binarySearch(int[] arr,int num){ 
            int start = 0;//起始位置
            int end = arr.length-1;
    
            //定义一个循环不断的折中寻找
            while (start <= end){ 
                //定位出中间元素的索引
                int middleIndex = (start + end)/2;
                //拿查找元素与中间元素比较
                if (num > arr[middleIndex]){ 
                    //当前元素大于中间元素，往右找，起始位置改变，等于中间位置+1
                    start = middleIndex+1;
                }else if(num < arr[middleIndex]){ 
                    //当前元素小于中间元素，往左找，末尾位置改变，等于中间位置-1
                    end = middleIndex-1;
                }else if (num == arr[middleIndex]){ 
                    return middleIndex;
                }
            }
            return -1;
        }
    
    }