/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
class BinarySearch {
 
    // 二分查找方法
    public static int binarySearch(int[] arr, int target) {
        int left = 0; // 定义左边界
        int right = arr.length - 1; // 定义右边界
 
        while (left <= right) { // 当左边界小于等于右边界时，继续查找
            int mid = left + (right - left) / 2; // 计算中间位置，避免大数溢出
            if (arr[mid] == target) { // 如果中间位置的元素正好是目标值，返回其索引
                return mid;
            } else if (arr[mid] < target) { // 如果中间位置的元素小于目标值，说明目标值在右半部分
                left = mid + 1;
            } else { // 如果中间位置的元素大于目标值，说明目标值在左半部分
                right = mid - 1;
            }
        }
        // 如果未找到目标值，返回-1
        return -1;
    }
 
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; // 有序数组
        int target = 9; // 要查找的目标值
        int result = binarySearch(arr, target); // 调用二分查找方法
        if (result != -1) {
            System.out.println("元素 " + target + " 在数组中的索引为：" + result);
        } else {
            System.out.println("数组中不存在元素 " + target);
        }
    }
}
 
 
 

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBCaW5hcnlTZWFyY2ggewoKICAgIC8vIOS6jOWIhuafpeaJvuaWueazlQogICAgcHVibGljIHN0YXRpYyBpbnQgYmluYXJ5U2VhcmNoKGludFtdIGFyciwgaW50IHRhcmdldCkgewogICAgICAgIGludCBsZWZ0ID0gMDsgLy8g5a6a5LmJ5bem6L6555WMCiAgICAgICAgaW50IHJpZ2h0ID0gYXJyLmxlbmd0aCAtIDE7IC8vIOWumuS5ieWPs+i+ueeVjAoKICAgICAgICB3aGlsZSAobGVmdCA8PSByaWdodCkgeyAvLyDlvZPlt6bovrnnlYzlsI/kuo7nrYnkuo7lj7PovrnnlYzml7bvvIznu6fnu63mn6Xmib4KICAgICAgICAgICAgaW50IG1pZCA9IGxlZnQgKyAocmlnaHQgLSBsZWZ0KSAvIDI7IC8vIOiuoeeul+S4remXtOS9jee9ru+8jOmBv+WFjeWkp+aVsOa6ouWHugogICAgICAgICAgICBpZiAoYXJyW21pZF0gPT0gdGFyZ2V0KSB7IC8vIOWmguaenOS4remXtOS9jee9rueahOWFg+e0oOato+WlveaYr+ebruagh+WAvO+8jOi/lOWbnuWFtue0ouW8lQogICAgICAgICAgICAgICAgcmV0dXJuIG1pZDsKICAgICAgICAgICAgfSBlbHNlIGlmIChhcnJbbWlkXSA8IHRhcmdldCkgeyAvLyDlpoLmnpzkuK3pl7TkvY3nva7nmoTlhYPntKDlsI/kuo7nm67moIflgLzvvIzor7TmmI7nm67moIflgLzlnKjlj7PljYrpg6jliIYKICAgICAgICAgICAgICAgIGxlZnQgPSBtaWQgKyAxOwogICAgICAgICAgICB9IGVsc2UgeyAvLyDlpoLmnpzkuK3pl7TkvY3nva7nmoTlhYPntKDlpKfkuo7nm67moIflgLzvvIzor7TmmI7nm67moIflgLzlnKjlt6bljYrpg6jliIYKICAgICAgICAgICAgICAgIHJpZ2h0ID0gbWlkIC0gMTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAvLyDlpoLmnpzmnKrmib7liLDnm67moIflgLzvvIzov5Tlm54tMQogICAgICAgIHJldHVybiAtMTsKICAgIH0KCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CiAgICAgICAgaW50W10gYXJyID0gezEsIDMsIDUsIDcsIDksIDExLCAxMywgMTUsIDE3LCAxOX07IC8vIOacieW6j+aVsOe7hAogICAgICAgIGludCB0YXJnZXQgPSA5OyAvLyDopoHmn6Xmib7nmoTnm67moIflgLwKICAgICAgICBpbnQgcmVzdWx0ID0gYmluYXJ5U2VhcmNoKGFyciwgdGFyZ2V0KTsgLy8g6LCD55So5LqM5YiG5p+l5om+5pa55rOVCiAgICAgICAgaWYgKHJlc3VsdCAhPSAtMSkgewogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIuWFg+e0oCAiICsgdGFyZ2V0ICsgIiDlnKjmlbDnu4TkuK3nmoTntKLlvJXkuLrvvJoiICsgcmVzdWx0KTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIuaVsOe7hOS4reS4jeWtmOWcqOWFg+e0oCAiICsgdGFyZ2V0KTsKICAgICAgICB9CiAgICB9Cn0KCgo=