美文网首页
二分查找

二分查找

作者: QinRenMin | 来源:发表于2018-03-28 20:55 被阅读0次

    解释:二分查找运用在生活的很多方面。例如猜数字游戏,在1到100中选择一个数字,然后进行猜测,用猜测的数字和已知进行比较大小,排除一半一半的可能性,这样最多7步,而采用自然的方法,需要很多次,因而二分查找的时间复杂度更低。
    前提:序列有序。
    代码实现:

    import java.util.*;
    import java.util.Scanner;
    class BinnarySearch 
    {
        public static void main(String[] args) 
        {
            Scanner input = new Scanner(System.in);
            int []arr = new int[7];
            System.out.println("请有序输入一串数字(从小到大)");
            for(int i = 0; i < arr.length; i++)
            {
                arr[i] = input.nextInt();
            }
            
            System.out.println("请输入要查询的数字");
            int n;
            n = input.nextInt();
            System.out.println("要查询的数字"+ n + "的位置是:"+Search(arr,n)+1);
        }           
        public static int  Search(int[] arr, int n)
        {
            int right = arr.length - 1;
            int left = 0;
            while(left <= right)
            {
                int mid = (right+left) / 2;
                if(n == arr[mid]) return mid;
                else if(n < arr[mid]) right = mid - 1;
                else    left = mid + 1;
            }
            return -1; //表示没有找到
        }
    }
    
    截图

    相关文章

      网友评论

          本文标题:二分查找

          本文链接:https://www.haomeiwen.com/subject/yynucftx.html