java实现二分查找及其变种

普通二分查找（查找等于指定值的索引下标）

非递归实现

public class Client {

  public static void main(String[] args) {
    int[] nums = {1, 3, 5, 7, 9, 10};
    System.out.println(binarySearch(nums, 5));
  }

  private static int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    //在区间[left,right]中查找target
    while (left <= right) {
      int middle = left + ((right - left) >> 1);
      if (nums[middle] > target) {
        right = middle - 1;
      } else if (nums[middle] < target) {
        left = middle + 1;
      } else {
        return middle;
      }
    }
    return -1;
  }
}

递归实现

public class Client2 {

  public static void main(String[] args) {
    int[] nums = {1, 3, 5, 7, 9, 10};
    System.out.println(binarySearch(nums, 10));
  }

  private static int binarySearch(int[] nums, int target) {
    return binarySearch(nums, 0, nums.length - 1, target);
  }

  private static int binarySearch(int[] nums, int left, int right, int target) {
    //在区间[left,right]中查找target
    if (left > right) {
      return -1;
    }
    int middle = left + ((right - left) >> 1);
    if (nums[middle] > target) {
      return binarySearch(nums, left, middle - 1, target);
    }
    if (nums[middle] < target) {
      return binarySearch(nums, middle + 1, right, target);
    }
    return middle;
  }
}

查找大于指定值的最小索引下标

public class Client3 {

  public static void main(String[] args) {
    int[] nums = {1, 1, 3, 3, 5, 5};
    for (int i = 0; i <= 6; i++) {
      System.out.println(binarySearch(nums, i));
      System.out.println(binarySearch2(nums, i));
    }
  }

  /**
   * 查找大于target的最小索引
   */
  private static int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    //在区间[left,right]中查找大于target的最小值，找不到的话right=nums.length
    while (left < right) {
      int middle = left + ((right - left) >> 1);
      if (nums[middle] > target) {
        //middle可能是大于target的最小值，也可能不是，所以右区间要包含middle
        right = middle;
      } else {
        left = middle + 1;
      }
    }
    return right == nums.length ? -1 : right;
  }

  /**
   * 另一种写法，更好理解
   */
  private static int binarySearch2(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    //在区间[left,right]中查找大于target的最小值
    while (left <= right) {
      int middle = left + ((right - left) >> 1);
      if (nums[middle] > target) {
        //如果已经查找到最左边或左边一个元素不满足，说明找到结果了
        if (middle == 0 || nums[middle - 1] <= target) {
          return middle;
        } else {
          right = middle - 1;
        }
      } else {
        left = middle + 1;
      }
    }
    return -1;
  }
}

查找小于指定值的最大索引下标

public class Client4 {

  public static void main(String[] args) {
    int[] nums = {1, 1, 3, 3, 5, 5};
    for (int i = 0; i <= 6; i++) {
      System.out.println(binarySearch(nums, i));
      System.out.println(binarySearch2(nums, i));
    }
  }

  /**
   * 查找小于target的最大索引
   */
  private static int binarySearch(int[] nums, int target) {
    int left = -1;
    int right = nums.length - 1;
    //在区间[left,right]中查找小于target的最大索引，找不到的话left=-1
    while (left < right) {
      //求中间值向上取整 [1,2]取2，默认是向下取整的
      int middle = left + ((right - left + 1) >> 1);
      if (nums[middle] < target) {
        left = middle;
      } else {
        right = middle - 1;
      }
    }
    return left;
  }

  /**
   * 另一种写法，更好理解
   */
  private static int binarySearch2(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    //在区间[left,right]中查找小于target的最大索引
    while (left <= right) {
      int middle = left + ((right - left) >> 1);
      //如果已经查找到最右边或右边一个元素不满足，说明找到结果了
      if (nums[middle] < target) {
        if (middle == nums.length - 1 || nums[middle + 1] >= target) {
          return middle;
        } else {
          left = middle + 1;
        }
      } else {
        right = middle - 1;
      }
    }
    return -1;
  }
}

这个二分查找变种和上一种类似，但是第一种写法有一个坑，就是当left和right相邻的时候，会死循环，这是因为默认求中位数是向下取整的，如数组[1,2]，向下取整取1，向上取整取2。

查找两个有序数组中第K大的值

public class Client5 {

  public static void main(String[] args) {
    int[] nums1 = {1, 3, 5};
    int[] nums2 = {2, 4, 6};
    System.out.println(findKthSmallest(nums1, nums2, 2));
  }

  private static int findKthSmallest(int[] nums1, int[] nums2, int k) {
    return findKthSmallest(nums1, 0, nums2, 0, k);
  }

  /**
   * 查找两个数组中第K小元素，K范围为[1,len]
   */
  private static int findKthSmallest(int[] nums1, int nums1Left, int[] nums2, int nums2Left,
      int k) {
    int len1 = nums1.length;
    int len2 = nums2.length;
    //第一个数组查找完，直接查找第二个数组
    if (nums1Left >= len1) {
      return nums2[nums2Left + k - 1];
    }
    //第二个数组查找完，直接查找第一个数组
    if (nums2Left >= len2) {
      return nums1[nums1Left + k - 1];
    }
    if (k == 1) {
      return Math.min(nums1[nums1Left], nums2[nums2Left]);
    }
    //中位数向下取整
    int middleVal1 =
        (nums1Left + k / 2 - 1 < len1) ? nums1[nums1Left + k / 2 - 1] : Integer.MAX_VALUE;
    int middleVal2 =
        (nums2Left + k / 2 - 1 < len2) ? nums2[nums2Left + k / 2 - 1] : Integer.MAX_VALUE;
    if (middleVal1 < middleVal2) {
      return findKthSmallest(nums1, nums1Left + k / 2, nums2, nums2Left, k - k / 2);
    } else {
      return findKthSmallest(nums1, nums1Left, nums2, nums2Left + k / 2, k - k / 2);
    }
  }

 /**
   * 查找两个数组中第K小元素，K范围为[1,len]，另一种解法，更好理解
   */
  private static int findKthSmallest2(int[] nums1, int[] nums2, int k) {
    k--;//[0,len-1]
    int len1 = nums1.length;
    int len2 = nums2.length;
    int cur1 = 0;
    int cur2 = 0;
    int cur3 = 0;
    while (cur1 < len1 && cur2 < len2) {
      if (nums1[cur1] < nums2[cur2]) {
        if (cur3 == k) {
          return nums1[cur1];
        }
        cur1++;
        cur3++;
      } else {
        if (cur3 == k) {
          return nums2[cur2];
        }
        cur2++;
        cur3++;
      }
    }
    while (cur1 < len1) {
      if (cur3 == k) {
        return nums1[cur1];
      }
      cur1++;
      cur3++;
    }
    while (cur2 < len2) {
      if (cur3 == k) {
        return nums2[cur2];
      }
      cur2++;
      cur3++;
    }
    return -1;
  }
}

在旋转排序数组中查找等于指定值的索引下标

public class Client6 {

  public static void main(String[] args) {
    System.out.println(search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));//4
    System.out.println(search(new int[]{0, 1, 2, 4, 5, 6, 7,}, 0));//0
    System.out.println(search(new int[]{4, 5, 6, 7, 0, 1, 2}, 3));//-1
  }

  public static int search(int[] nums, int target) {
    if (nums.length == 0) {
      return -1;
    }
    int minIndex = findMinIndex(nums);
    int res = binarySearch(nums, 0, minIndex - 1, target);
    if (res == -1) {
      res = binarySearch(nums, minIndex, nums.length - 1, target);
    }
    return res;
  }

  //找到最小值的索引下标
  private static int findMinIndex(int[] nums) {
    int len = nums.length;
    int left = 0;
    int right = len - 1;
    int target = nums[len - 1];
    while (left <= right) {
      int middle = (left + right) / 2;
      if (nums[middle] <= target) {
        //中间值小于等于末尾值，说明旋转点在左边
        if (middle == 0 || nums[middle - 1] > target) {
          return middle;
        } else {
          right = middle - 1;
        }
      } else {
        left = middle + 1;
      }
    }
    return -1;
  }

  private static int binarySearch(int[] nums, int left, int right, int target) {
    while (left <= right) {
      int middle = (left + right) / 2;
      if (nums[middle] > target) {
        right = middle - 1;
      } else if (nums[middle] < target) {
        left = middle + 1;
      } else {
        return middle;
      }
    }
    return -1;
  }

}

先找到旋转点，在旋转点的左边和右边分别进行普通的二分查找。