教育改变生活

标题: Java编程-二分查找 [打印本页]

作者: 一秉 时间: 2020-8-28 16:25
标题: Java编程-二分查找
题目描述：
请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
示例1
输入：5,4,[1,2,4,4,5]
输出：3

实现代码：
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) {
      // write code here
      if(a==null || n==0 || a[n-1] < v) return n+1;
      if(a[0]>=v) return 1;
      int middle = 0;
      int left = 0,right = n-1;
      while(left <= right){
         middle = (left+right)/2;
         if(a[middle] >= v){
            // 中间值大于v，去左边区域继续查找
            // 若该数左边即为小的值，则此时middle+1为所要找的位置
            if(middle==0 || a[middle-1]<v) return middle+1;
            right = middle-1;
         }else{
            // 中间值小于v，右边区域查找
            left = middle+1;
         }
      }
      return n+1;
}
}

欢迎光临教育改变生活 (http://bbs.goldoar.com/)