编写二分查找和使用集合类的二分查找实现

Love The Way You Lie 2021-09-21 22:22 251阅读 0赞

# 如下所示，编写二分查找和使用集合类的二分查找实现 #

import java.util.Arrays;
    import java.util.Scanner;
    
    public class DigitalGame { 
        public static void main(String[] args) { 
            int[] arr = { 8,4,2,123,344,12};
    
            DigitalGame digitalGame = new DigitalGame();
            digitalGame.answer3(arr);
            digitalGame.binarySearch(arr,12);
    
            System.out.println(Arrays.toString(arr));
        }
    
        /** * 猜数字游戏，判断数组中是否存在 * 使用二分法进行判断是否存在 * @param arr */
        private void answer3(int[] arr){ 
            Arrays.sort(arr);
            Scanner scanner = new Scanner(System.in);
            System.out.print("请猜数字： ");
            int target = scanner.nextInt();
            int i = Arrays.binarySearch(arr, target);
            if (i>=0){ 
                System.out.println("该数存在");
            }
            System.out.println("该数不存在");
        }
    
        //下方自己实现的二分查找，应该不合题意——————————————————————————————————————————
    
        /** * 二分查找方法 * @param arr 查找的数组 * @param target 查找的目标 * @return 返回查找的结果，为true表示存在 */
        public Boolean binarySearch(int[] arr,int target){ 
            //首先对数组进行排序
            Arrays.sort(arr);
            //查找是否存在,定义两个指针 指向数组
            int firstPoint = 0;
            int lastPoint = arr.length-1;
            int midPoint = (firstPoint+lastPoint)/2;
            while (firstPoint<=lastPoint){ 
                if (arr[midPoint]>target){ 
                    lastPoint = midPoint-1;
                }else { 
                    firstPoint = midPoint+1;
                }
                if (arr[midPoint] == target){ 
                    return true;
                }
                midPoint = (firstPoint+lastPoint)/2;
            }
            return false;
        }
    }