LeetCode T34 二分查找

一道二分查找的题目，在有重复值的情况下查找两侧边界，但是感觉理解不太成熟，写的也不够清楚……可以略过这篇了。

T34题目

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

分析

朴实无华的二分查找（循环版）

pulic int binnarySearch(int[] nums, int target, int start,int end) {


       while(start<=end)
       {
           int mid = (start+end)/2;
          if(nums[mid]>target)
              end=mid-1;
          else if (nums[mid]<target)
              start=mid+1;
          else
              return target;
       }
       return -1;

}

• 注意边界的处理
• 无法处理有重复值的情况

处理有重复值时的二分查找

题目中要处理有重复值的情况，查找左边界和右边界的方法是不一样的。

查找左边界

区别就在于，当target=mid时，mid不一定是左边界。所以要把target=mid的情况放进区间里,而不能查找到target=mid就返回这个mid。

• 查找大于等于target的mid值，假设其为左边界。如果在mid的左边，也就是[start，mid-1]中还有大于等于target的mid值，就更新左边界。
• 如果target不存在，最后返回的值是第一个大于target的值。

   public int binarySearch(int[] nums, int target, r) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

查找右边界

• 查找大于target的mid值，假设其为ans，即右边界+1(其实找的是第一个大于target的值）。如果在mid左边还有大于target的值，就更新ans。

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target )
            {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }