【Java每日一题,左二分查找】Where is the Marble?

简介: 【Java每日一题,左二分查找】Where is the Marble?

Introduction

现有 N 个大理石,每个大理石上写了一个非负整数。首先请你将这 N 块大理石按照它们上面所写数字的大小从小到大排序,然后按照排序后的顺序把这 N 个大理石从 1 ~ N 编号。之后请你回答 Q 个询问,每个询问问是否存在一个大理石上写着某个整数 x,如果存在,请你回答写着整数 x 的编号最小的大理石的编号,如果不存在,请你输出 x not found。


Input

有多组数据。

每组数据第一行包括两个整数 N,Q,当输入为 N = 0, Q = 0 时,表示结束。

否则接下来 Q 行,每一行包括一个数字 x,表示询问。


Output

对于每组测试数据,首先输出 “Case# XX”,XX 为测试数据编号,按读入顺序由 1 开始递增。

然后输出的话,下面的案例很清晰了。


Sample

input

4 1
2
3
5
1
5
5 2
1
3
3
3
1
2
3
0 0

output

CASE# 1:
5 found at 4
CASE# 2:
2 not found
3 found at 3

Solution

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int index=1;
        while (true){
            int n=s.nextInt();int m=s.nextInt();
            if(n==0&&m==0)break;
            int[] arr=new int[n];
            for(int i=0;i<n;i++){
                arr[i]=s.nextInt();
            }
            Arrays.sort(arr);
            System.out.println("CASE# "+index+":");
            for(int j=0;j<m;j++){
                int k=s.nextInt();
                int i = binarySearch(arr, k);
                if(i==-1){
                    System.out.println(k+" not found");
                }else {
                    System.out.println(k+" found at "+i);
                }
            }
            index++;
        }
    }
    static int binarySearch(int[] arr,int k){
        int low=0,high=arr.length-1;
        while (low<high){
            int mid=(low+high)>>1;
            int key=arr[mid];
            if(k==key){
                high=mid;
            }else if(k<key) {
                high=mid-1;
            }else {
                low=mid+1;
            }
        }
        if(arr[low]!=k){
            return -1;
        }
        return low+1;
    }
}

Experience

第一次没有使用Arrays自带的二分查找的函数,因为要实现左二分的话,最好自己来实现。发现也没花多少时间。

相关文章
|
7月前
|
Java
java实现二分查找
java实现二分查找
48 0
|
2月前
|
Java
在 Java 中实现二分查找法
【10月更文挑战第9天】
33 1
|
2月前
|
算法 Java
java冒泡排序与二分查找(详解)
java冒泡排序与二分查找(详解)
40 4
|
5月前
|
算法 Java
Java 使用二分查找快速定位元素位置
Java 使用二分查找快速定位元素位置
23 0
|
6月前
|
存储 算法 Java
Java查找算法概览:二分查找适用于有序数组,通过比较中间元素缩小搜索范围;哈希查找利用哈希函数快速定位,示例中使用HashMap存储键值对,支持多值关联。
【6月更文挑战第21天】Java查找算法概览:二分查找适用于有序数组,通过比较中间元素缩小搜索范围;哈希查找利用哈希函数快速定位,示例中使用HashMap存储键值对,支持多值关联。简单哈希表实现未涵盖冲突解决和删除操作。
61 1
|
6月前
|
Java
二分查找-非递归(java)
二分查找-非递归(java)
|
6月前
|
Java
二分查找-递归(java)
二分查找-递归(java)
|
6月前
|
人工智能 算法 Java
二分查找Java版
二分查找Java版
38 0
|
6月前
|
Java
Java二分查找小例子
Java二分查找小例子
22 0
|
7月前
|
存储 算法 Java
二分查找(Java) 详细讲解 一文足矣
二分查找(Java) 详细讲解 一文足矣