BinarySearchTest

package com.aseit;

/**
 * Created with IntelliJ IDEA.
 * User: @ziyu  freedomziyua@gmail.com
 * Date: 2019-03-27
 * Time: 19:56
 * Description:
 * 在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回 -1。
 * 样例
 * 样例 1：
 * <p>
 * 输入：nums = [1,2,2,4,5,5], target = 2
 * 输出：1 或者 2
 * 样例 2：
 * <p>
 * 输入：nums = [1,2,2,4,5,5], target = 6
 * 输出：-1
 * 挑战
 * O(logn) 的时间
 */

import java.util.Scanner;

/**
 * 解析：二分查找，首先是数组已经是排序好的。
 */
public class BinarySearchTest {

    public static void main(String args[]) {

        int[] arr = new int[6];
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        int key = sc.nextInt();
        int a = search(arr, key);
        System.out.println(a);
    }

    public static int search(int[] arr, int key) {
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            int middle = start + (end-start) / 2;

            //目标元素比中值小的时候则最后一个元素左移
            if (key < middle) {
                end = middle - 1;
            } else if (key > middle) {
                start = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

}