二分查找

import java.util.*;

public class Solution {
	public static void main(String[] args) {
		int n,v;
		int [] a;
		Scanner reader = new Scanner(System.in);
		System.out.println("请输入数组长度：");
		n=reader.nextInt();
		a=new int[n];
		for(int i=0;i<a.length;i++)
			a[i]=reader.nextInt();
		System.out.println("请输入要查找的值：");
		v=reader.nextInt();
		try {System.out.println(upper_bound_(n, v, a) );}catch(Exception e) {
			e.printStackTrace();
		}	
	}
	public static int upper_bound_(int n, int v, int[] a) {
		int key;
		int min=0,max=a.length-1;
		if(a.length>0) {
			while(min<=max) {
					key=(min+max)/2;
					if(v==a[key]) {
                                        //找到与v相等还得看key-1是否与v相等，因为题目说的是第一个
						int i=key;
						do {
								i--;
							
						}while(v==a[i]);
						return i+2;
					}
						
					else if(v>a[key])
						min=key+1;
					
					else max=key-1;
				}
		}
                //找不到比较是否比a[0]还小，还小返回1；
		if(v<a[0])
			return 1;
                //否则返回数组长度+1；
		else
			return a.length+1;	
	}

}

import java.util.Scanner;

public class Main {
    private static final String SPLIT_SYMBOL = "\\[";
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] firstPart = line.split(SPLIT_SYMBOL)[0].split(",");
        String[] secondPart = line.split(SPLIT_SYMBOL)[1].split("\\]")[0].split(",");
        int originArrLength = Integer.parseInt(firstPart[0]);
        int toFindNum = Integer.parseInt(firstPart[1]);

        int[] baseArr = new int[originArrLength];
        for (int i = 0; i < secondPart.length; i++) {
            baseArr[i] = Integer.parseInt(secondPart[i]);
        }

        System.out.print(findPosition(originArrLength, toFindNum, baseArr));
    }

    private static int findPosition(int originArrLength, int toFindNum, int[] baseArr) {
        int arrLength = baseArr.length;
        if (toFindNum > baseArr[arrLength - 1]) {
            return originArrLength + 1;
        }
        if (toFindNum <= baseArr[0]) {
            return 1;
        }
        // 正常二分逻辑
        return method(toFindNum, baseArr, arrLength);
    }
    private static int method(int toFindNum, int[] baseArr, int arrLength) {
        int tempNum = baseArr[arrLength / 2];
        int topSide = arrLength;
        int bottomSide = 0;
        int currentUseNum = arrLength / 2;
        while(toFindNum != tempNum) {
            if (toFindNum < tempNum) {
                currentUseNum = (bottomSide + currentUseNum) / 2;
                tempNum = baseArr[currentUseNum];
                topSide = currentUseNum;
                continue;
            }
            currentUseNum = (topSide + currentUseNum) / 2;
            tempNum = baseArr[currentUseNum];
            bottomSide = currentUseNum;
        }
        int findFirstTestNum = currentUseNum;
        if (toFindNum == tempNum) {
            while (findFirstTestNum > 0) {
                if (baseArr[--findFirstTestNum] == toFindNum) {
                    continue;
                }
                break;
            }
            return findFirstTestNum + 2;
        }
        return arrLength + 1;
    }
}

import java.util.*;


public class Solution {
    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型一维数组 有序数组
     * @return int整型
     */
    public int upper_bound_ (int n, int v, int[] a) {
        if(n<=0 || a==null || a.length==0)
            return 1;
        
        int low=0, high=a.length-1, idx=0;
        while(low <= high) {
            int mid = low + (high-low)/2;
            if(a[mid] < v){
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        return low+1;
    }
}

    public int upper_bound_ (int n, int v, int[] a) {
        int left = 0;
        int right = n;
       while(left < right){
           int mid = (right + left) / 2;
           if(a[mid] >= v){
               right = mid;
           }else if(a[mid] < v){
               left = mid + 1;
           }
       }
       return left;
       // 牛客需要返回 return left + 1;
    }

    public int lower_bound_ (int n, int v, int[] a) {
        int left = 0;
        int right = n;
       while(left < right){
           int mid = (right + left) / 2;
           if(a[mid] <= v){
               left = mid + 1;
           }else if(a[mid] > v){
               right = mid;
           }
       }
       return left - 1;
    }

import java.util.*;


public class Solution {
    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型一维数组 有序数组
     * @return int整型
     */
    public int upper_bound_ (int n, int v, int[] a) {
        int result = Integer.MAX_VALUE;
        int left = 0;
        int right = n - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(a[mid] >= v) {
                result = Math.min(result, mid);
                //尝试找更小的
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result == Integer.MAX_VALUE ? n + 1 : result + 1;
    }
}

import java.util.*;


public class Solution {
    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型一维数组 有序数组
     * @return int整型
     */
    public int upper_bound_ (int n, int v, int[] a) {
        int i = 0, j = n-1;
        int mid;
        while(i <= j) {
            mid = (i + j) >>> 1;
            if (a[mid] == v) {
                //怕前面会有重复的数字出现，所以进行一次while，找出第一个该数的位置
                while(a[mid - 1] == v) {
                    mid--;
                }
                // 输出的位置从1开始，但是实际从0开始，所以要 + 1
                return mid + 1;
            }else if(a[mid] < v) {
                i =mid + 1;
            }else {
                j = mid -1;
            }
        }
        if(j < 0) {
            return 1;
        }else if(i >= n) {
            return n + 1;
        }else{
            // 此时 i < j
            if(a[j] > v){
                return j + 1;
            }else if(a[i] > v) {
                return i + 1;
            }
            return n + 1;
        }
    }
}