class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans=new int[2];
        ans[0]=searchRangeLeft(nums,target);
        ans[1]=searchRangeRight(nums,target);
        return ans;
    }
    public int searchRangeLeft(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else if(mid==0 || nums[mid-1]!=target){
                return mid;
            }else{
                right=mid-1;
            }
        }
        return -1;
    }
    public int searchRangeRight(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else if(mid==nums.length-1 || nums[mid+1]!=target){
                return mid;
            }else{
                left=mid+1;
            }
        }
        return -1;
    }
}

注意：如果你找到一个target，然后向左向右线性查找是不对的，这样时间会退化为O(N)，和二分的本意违背了。

3.4泛化二分的概念

看到第一节，可能大部分人都没有问题；

看到第二节，可能对有些写二分总有bug的同学有一些帮助，会觉得”细节确实需要注意“，二分查找从此要一次就bug free；

至此，我们看一下百度百科对二分的定义：

简单来说，我们介绍的就是在顺序存储结构（数组）有序的情况下进行二分查找。

从第四节开始，我们介绍的就不是传统意义上的二分查找了，不局限于”有序“，甚至不局限于线性结构，while循环里判断向左还是向右搜索的条件也不会这么单一，而更可能是这样：

? ? ? ? while (范围没有缩小为0) {
? ? ? ? ? ? if (满足某种条件) {
? ? ? ? ? ? ? ? 排除一半答案
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? 排除另一半答案
? ? ? ? ? ? }
? ? ? ? }

我们的思想是：只要可以通过正确逻辑，用二分思想正确的缩小查找范围，都称之为二分。

下面就来体会一下什么是二分思想：

我们正在玩一个猜数字游戏。 游戏规则如下：
我从?1?到?n?选择一个数字。 你需要猜我选择了哪个数字。
每次你猜错了，我会告诉你这个数字是大了还是小了。
你调用一个预先定义好的接口?guess(int num)，它会返回 3 个可能的结果（-1，1?或 0）：

-1 : 我的数字比较小
?1 : 我的数字比较大
?0 : 恭喜！你猜对了！
示例 :

输入: n = 10, pick = 6输出: 6

/* The guess API is defined in the parent class GuessGame.
   @param num, your guess
   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
      int guess(int num); */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int low = 1;
        int high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int res = guess(mid);
            if (res == 0)
                return mid;
            else if (res < 0)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
}

public class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] > nums[mid + 1])
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
}

class Solution {
    public int findMin(int[] nums) {
        if(nums.length==1)return nums[0];
        if(nums[0]<nums[nums.length-1])return nums[0];
        int left=0;
        int right=nums.length-1;
        int mid=0;
        while(left<right){
            mid=(left+right)/2;
            if(nums[mid]>=nums[0]){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return nums[right];
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int start = 0;
        int end = row * col - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid / col][mid % col] == target)return true;
            else if (matrix[mid / col][mid % col] > target)end = mid - 1;
            else start = mid + 1;
        }
        return false;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public int closestValue(TreeNode root, double target) {
    int val, closest = root.val;
    while (root != null) {
      val = root.val;
      closest = Math.abs(val - target) < Math.abs(closest - target) ? val : closest;
      root =  target < root.val ? root.left : root.right;
    }
    return closest;
  }
}

?
public class Demo {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}
//返回结点个数
	public static int nodeNum(Node head) {
		if (head == null) {
			return 0;
		}
		return bs(head, 1, mostLeftLevel(head, 1));
	}
//返回根为node，当前层数为l，总深度为h的结点个数
	public static int bs(Node node, int l, int h) {
		if (l == h) {
			return 1;
		}
		if (mostLeftLevel(node.right, l + 1) == h) {             //右子树最深一行最左为空
			return (1 << (h - l)) + bs(node.right, l + 1, h);    //右bs+左子树结点个数
		} else {                                                 //右子树最深一行最左不为空
			return (1 << (h - l - 1)) + bs(node.left, l + 1, h);//左bs+右子树结点个数
		}
	}
//计算树的高度
	public static int mostLeftLevel(Node node, int level) {
		while (node != null) {
			level++;
			node = node.left;
		}
		return level - 1;
	}

	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		System.out.println(nodeNum(head));
	}
}
?

public class Solution {
 
    public int mySqrt(int x) {
        long left = 0;
        long right = Integer.MAX_VALUE;
        while (left < right) {
            long mid = (left + right + 1) >>> 1;
            long square = mid * mid;
            if (square > x) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return (int) left;
    }
}

#include <cstdio>
#include <cmath>
using namespace std;
const int M=10005;
const double inf=200005.0;
double L[M];
int n,k;
bool judge(double x)//判断解是否可行
{
    int num=0;
    for(int i=0;i<n;i++)num+=(int)(L[i]/x);
    return num>=k;
}
void solve()//二分答案
{
    double left=0,right=inf;
    for(int i=0;i<100;i++) //代替while(r>l) 避免了精度问题
    { //1次循环可以把区间缩小一半，100次可以达到10^(-30)的精度
        double mid=(left+right)/2;
        if(judge(mid)) left=mid;
        else right=mid;
    }
    printf("%.2f\n",floor(right*100)/100);
}
int main()
{
    while(scanf("%d%d",&n,&k)!=-1)
    {
        for(int i=0;i<n;i++)scanf("%lf",&L[i]);
        solve();
    }
}