[javaSE] 數組（查找-二分查找），javase數組

[javaSE] 數組（查找-二分查找），javase數組

前提數組必須是有序的

定義最小，最大，中間的角標索引

        int min,max,mid;
        min=0;
        max=arr.length-1;
        mid=(min+max)/2;

上面的索引需要變化，使用循環，條件：當中間值不等於目標值時

        int min,max,mid;
        min=0;
        max=arr.length-1;
        mid=(min+max)/2;
        while(arr[mid]!=key){
            if(key<arr[mid]){
                
            }else if(arr[mid]<key){
                
            }
        }

當中間值大於目標值時，最大角標移動到中間角標-1位置

當中間值小於目標值時，最小角標移動到中間角標+1位置

中間角標繼續二分

        int min,max,mid;
        min=0;
        max=arr.length-1;
        mid=(min+max)/2;
        while(arr[mid]!=key){
            if(key<arr[mid]){
                max=mid-1;
            }else if(arr[mid]<key){
                min=mid+1;
            }
            mid=(min+max)/2;
        }
        return mid;

此時的代碼有問題，當找不到目標時，會陷入死循環，加一個判斷

如果一直找不到，最小角標和最大角標會錯位

        int min,max,mid;
        min=0;
        max=arr.length-1;
        mid=(min+max)/2;
        while(arr[mid]!=key){
            if(key<arr[mid]){
                max=mid-1;
            }else if(arr[mid]<key){
                min=mid+1;
            }
            if(min>max) return -1;
            mid=(min+max)/2;
        }
        return mid;

java版：

public class ArrayDemo {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] arr=new int[]{1,4,6,7,8,9};
        System.out.println("索引:"+keySearch(arr,7));//索引:3
        System.out.println("索引:"+helfSearch(arr,7));//索引:3
    }
    /**
     * 二分查找
     * @param arr
     * @param key
     * @return
     */
    public static int helfSearch(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]){
                max=mid-1;
            }else if(arr[mid]<key){
                min=mid+1;
            }
            if(min>max) return -1;
            mid=(min+max)/2;
        }
        return mid;
    }
    /**
     * 獲取該值在數組中第一次出現的位置
     * @param arr
     * @param num
     * @return
     */
    public static int keySearch(int[] arr,int num){
        for(int i=0;i<arr.length;i++){
            if(arr[i]==num){
                return i;
            }
        }
        return -1;
    }
}

PHP版：

<?php
class ArrayDemo{
    public static function main(){
        $arr=array(1,4,6,7,8,9);
        echo "索引:".ArrayDemo::keySearch($arr,7);//索引:3
        echo "索引:".ArrayDemo::helfSearch($arr,7);//索引:3
    }
    /**
     * 二分查找
     * @param arr
     * @param key
     * @return
     */
    public static function helfSearch($arr,$key){
        $min=0;
        $max=count($arr)-1;
        $mid=ceil(($min+$max)/2);
        while($arr[$mid]!=$key){
            if($key<$arr[$mid]){
                $max=$mid-1;
            }else if($arr[$mid]<$key){
                $min=$mid+1;
            }
            $mid=ceil(($min+$max)/2);
            if($min>$max) return -1;
        }
        return $mid;
    }
    /**
     * 獲取該值在數組中第一次出現的位置
     * @param arr
     * @param num
     * @return
     */
    public static function keySearch($arr,$key){
        for($i=0;$i<count($arr);$i++){
            if($arr[$i]==$key){
                return $i;
            }
        }
        return -1;
    }
}

ArrayDemo::main();