数据结构与算法——Java实现 3.二分查找—

放下不切实际的幻想，放下无法更改的过去，行云流水，任其行之

—— 24.8.31

一、二分查找——Java基础版

Java中的API——Arrays.binarySearch(数组，目标值)

返回的结果是插入点的位置

若在目标数组中找不到元素，则返回的是负的（插入该点的位置+1）

+1，是为了避免在第一个位置插入时，返回0与查找元素刚好处在第一个位置重复的这种情况，+1可以分辨这两种情况，观察是否返回的是负数

java">import java.util.Arrays;public class demo2BinarySearchJava {public static void main(String[] args) {int[] arr = {1,2,3,4,5,6,7,8,9,10};int target = -1;int res = Arrays.binarySearch(arr, target);// 找不到时，会返回负的(插入点的位置+1)：-（low+1）    +1是为了区分在第一个0位置插入的情况System.out.println("res: " + res); // 11// 返回点的插入位置用i变量表示就可以if(res < 0){// Math.abs：绝对值函数// 插入点索引insertint insert = Math.abs(res+1);// 创建数组Bint[] arrB = new int[arr.length+1];// 数组拷贝 被拷贝数组 拷贝位置 目标新数组 拷贝起始位置 拷贝数据的长度System.arraycopy(arr,0,arrB,0,insert);// 将被插入点位置元素改为插入元素arrB[insert] = target;// 数组拷贝 将新插入元素后位置的函数插入到插入点位置System.arraycopy(arr,insert,arrB,insert+1,arr.length-insert);System.out.println(Arrays.toString(arrB));}}
}

二、二分查找——找到重复元素中元素的位置

1.找到重复元素中最左侧第一个出现元素的位置

当数组中存在多个待查找的元素时，观察寻找最左侧元素的位置

若是找到则返回元素位置，若是找不到则返回-1

java">    public static int binarySearchLeftmost(int[] arr, int key) {int i = 0,j = arr.length-1;int candidate = -1; // 记录候选位置while (i <= j) {int m = (i + j) >>> 1;if (key < arr[m]) {j = m - 1;} else if (arr[m] < key) {i = m + 1;}else {// 记录侯选位置candidate = m;j = m-1;}}return candidate;}

2.找到重复元素中最右侧第一个出现元素的位置

当数组中存在多个待查找的元素时，观察寻找最右侧元素的位置

若是找到则返回元素位置，若是找不到则返回-1

java">    // 重复元素中找到最右
public static int binarySearchRightmost(int[] arr, int key) {int i = 0,j = arr.length-1;int candidate = -1;while (i <= j) {int m = (i + j) >>> 1;if (key < arr[m]) {j = m - 1;}else if (arr[m] < key) {i = m + 1;}else {candidate = m;i = m + 1;}}return candidate;
}

3.返回值的优化——返回插入位置

① 最左侧查找优化

当数组中存在多个待查找的元素时，观察寻找最左侧元素的位置

若是找到则返回元素位置，若是找不到则返回插入时的插入位置

java">    public static int binarySearchLeftmost(int[] arr, int key) {int i = 0,j = arr.length-1;while (i <= j) {int m = (i + j) >>> 1;if (key <= arr[m]) {// 记录侯选位置j = m - 1;} else {// 记录侯选位置i = m + 1;}}// i代表的是 > target目标值的最左侧索引位置return i;}

② 最右侧查找优化

当数组中存在多个待查找的元素时，观察寻找最右侧元素的位置

若是找到则返回元素位置，若是找不到则返回插入时的插入位置

java">    // 重复元素中找到最右public static int binarySearchRightmost(int[] arr, int key) {int i = 0,j = arr.length-1;while (i <= j) {int m = (i + j) >>> 1;if (key < arr[m]) {j = m - 1;}else {i = m + 1;}}// i - 1表示小于等于目标并且最靠近右边的索引位置return i - 1;}

③ 测试

java">    public static void main(String[] args) {int[] arr = {1,2,4,5,6,7,9};System.out.println(binarySearchLeftmost(arr,3));System.out.println(binarySearchRightmost(arr,8));System.out.println(binarySearchLeftmost(arr,4));System.out.println(binarySearchRightmost(arr,5));}

三、最左查询和最右查询的应用

二分查找 Leftmost
        Params：a-待查找的升序数组

          target-待查找的目标值

        Returns:
                        返回 ≥ target 的最靠左索引

二分查找 Rightmost

        Params：a-待查找的升序数组

                        target-待查找的目标值
        Returns:

                        返回 ≤target 的最靠右索引