二分查找&变体

• 二分查找其实占用的内存比较少，但是如果是寻找给定值的数据时，二分查找虽然占用内存小，但是用散列表或者二叉搜索树代替。
• 二分查找不适合非数组，也不适合数组一直在频繁的插入删除（因为要频繁排序）
• 二分查找的变体情况用的比较多，也就是搜索近似。

代码&测试如下：

import java.util.*;

public class BinSearch
{
    //测试的主类
    public static void main(String args[])
    {
        // int[] arr=new int[10];
        // for(int i=0;i<10;++i)
        //     arr[i]=(int)(Math.random()*20); 
        // Arrays.sort(arr);       
        // for(int i=0;i<arr.length;++i)
        //     System.out.print(arr[i]+" ");
        // System.out.println();
        // //随机生成10个数，测试b1,b2
        // System.out.println(bSearch(arr,3));
        // System.out.println(bSearch2(arr,3));
        // //测试哦bSearch3
        int[] arr2={1,1,1,1,2,2,2,3,3,3};
        // System.out.println(bSearch3(arr2,1));
        // System.out.println(bSearch3(arr2,2));
        // System.out.println(bSearch3(arr2,3));
        //测试b4
        // System.out.println(bSearch4(arr2,1));
        // System.out.println(bSearch4(arr2,2));
        // System.out.println(bSearch4(arr2,3));
        // System.out.println(bSearch4(arr2,4));
        //测试b5
        // System.out.println(bSearch5(arr2,1));
        // System.out.println(bSearch5(arr2,2));
        // System.out.println(bSearch5(arr2,3));
        // System.out.println(bSearch5(arr2,4));
        //测试b6
        System.out.println(bSearch6(arr2,1));
        System.out.println(bSearch6(arr2,2));
        System.out.println(bSearch6(arr2,3));
        System.out.println(bSearch6(arr2,4));
    }
    //第一种二分搜索，适用与判断数组中有没有这个元素
    public static boolean bSearch(int[] arr,int num)
    {
        int low=0;
        int high=arr.length-1;
        int mid;
        while(low<=high)
        {
            //mid=(low+high)/2;
            mid=low+((high-low)>>2);
            if(arr[mid]==num)
                return true;
            else if(arr[mid]<num)
                low=mid+1;
            else
                high=mid-1;
        }
        return false;
    }
    //第二种二分搜索，适用无重复元素，搜索num出现的唯一的下标
    public static int bSearch2(int[] arr,int num)
    {
        int low=0;
        int high=arr.length-1;
        int mid;
        while(low<=high)
        {
            //mid=(low+high)/2;
            mid=low+((high-low)>>2);
            if(arr[mid]==num)
                return mid;
            else if(arr[mid]<num)
                low=mid+1;
            else
                high=mid-1;
        }
        return -1;
    }
    //第三种二分搜索，寻找有重复元素中的第一个元素的下标
    public static int bSearch3(int[] arr,int num)
    {
        int low=0;
        int high=arr.length-1;
        int mid;
        while(low<=high)
        {
            //mid=(low+high)/2;
            mid=low+((high-low)>>2);
            if(arr[mid]>num)
                high=mid-1;
            else if(arr[mid]<num)
                low=mid+1;
            else
            {
                if(mid==0||arr[mid-1]!=num)
                    return mid;
                else
                    high=mid-1;
            }
        }
        return -1;
    }
    //第四种二分搜索，寻找有重复元素中的最后一个元素的下标
    public static int bSearch4(int[] arr,int num)
    {
        int low=0;
        int high=arr.length-1;
        int n=arr.length;
        int mid;
        while(low<=high)
        {
            //mid=(low+high)/2;
            mid=low+((high-low)>>2);
            if(arr[mid]>num)
                high=mid-1;
            else if(arr[mid]<num)
                low=mid+1;
            else
            {
                if(mid==n-1||arr[mid+1]!=num)
                    return mid;
                else
                    low=mid+1;
            }
        }
        return -1;
    }
    //第五种二分搜索，寻找第一个大于等于num的元素
    public static int bSearch5(int[] arr,int num)
    {
        int low=0;
        int high=arr.length-1;
        int n=arr.length;
        int mid;
        while(low<=high)
        {
            //mid=(low+high)/2;
            mid=low+((high-low)>>2);
            if(arr[mid]>=num)
            {
                if(mid==0||arr[mid-1]<num)
                    return mid;
                else
                    high=mid+1;
            }
            else
                low=mid+1;
        }
        return -1;
    }
    //第六种二分搜索，寻找最后一个小于等于num的元素
    public static int bSearch6(int[] arr,int num)
    {
        int low=0;
        int high=arr.length-1;
        int n=arr.length;
        int mid;
        while(low<=high)
        {
            //mid=(low+high)/2;
            mid=low+((high-low)>>2);
            if(arr[mid]<=num)
            {
                if(mid==n-1||arr[mid+1]>num)
                    return mid;
                else
                    low=mid+1;
            }
            else
                high=mid-1;
        }
        return -1;
    }
}