题目如下：

Binary Search

For a given sequence A={a0,a1,...,an−1}A={a0,a1,…,an−1} which is sorted by ascending order, find a specific value kkgiven as a query.

Input

The input is given in the following format.

nn
a0a1,...,an−1a0a1,...,an−1
qq
k1k1
k2k2
:
kqkq

The number of elements nn and each element aiai are given in the first line and the second line respectively. In the third line, the number of queries qq is given and the following qq lines, qq integers kiki are given as queries.

Output

For each query, print 1 if any element in AA is equivalent to kk, and 0 otherwise.

Constraints

  • 1≤n≤100,0001≤n≤100,000
  • 1≤q≤200,0001≤q≤200,000
  • 0≤a0≤a1≤...≤an−1≤1,000,000,0000≤a0≤a1≤…≤an−1≤1,000,000,000
  • 0≤ki≤1,000,000,0000≤ki≤1,000,000,000

Sample Input 1

4
1 2 2 4
3
2
3
5

Sample Output 1

1
0
0
不刷不知道，一刷吓一跳，错了好几遍好AC。主要错在找端点的位置。
我的代码如下：
import java.util.Arrays;
import java.util.Scanner;

public class Main
{
    static final int MAX = 100005;
    static int num[] = new int[MAX];
    static int n;
    public static void main(String []args)
    {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        for(int i = 0; i < n; i++)
        {
            num[i] = cin.nextInt();
        }
        Arrays.sort(num, 0,n);//先按从小到大排序
        int q = cin.nextInt();
        for(int i = 0; i < q; i++)
        {
            int a = cin.nextInt();
            System.out.println(Search(a));
        }
    }
    static int Search(int a)
    {
        int left = 0;
        int right = n-1;
        while(left != right)
        {
            int mid = (right+left)/2;
            if(left + 1 == right)
            {
                if(num[left] == a || num[right] == a)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
            else if(num[mid] > a)
            {
                right = mid;
            }
            else if(num[mid] == a) 
            {
                return 1;
            }
            else
            {
                left = mid;
            }
        }
        if(num[left] == a)
        {
            return 1;
        }
        return 0;
    }
}

 

版权声明：本文为674001396long原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/674001396long/p/10013043.html