目录

一、递归实现

二、非递归实现

三、二分查找的优化版本

四、二分查找的变性

1、 查找第一个值等于给定值的情况

2、 查找最后一个值等于给定值的情况

3、查找第一个大于等于给定值的情况

思考继续变性：查找第一个大于给定值的情况，特殊考虑等于情况即可

4、查找最后一个小于等于给定值的情况

思考继续变性：查找最后一个小于给定值的情况，特殊考虑等于情况即可

---

一、递归实现

public class BinarySearch {
    public static int recursiveBinarySearch(int[] arr, int target) {
        return recursiveBinarySearchHelper(arr, target, 0, arr.length - 1);
    }

    private static int recursiveBinarySearchHelper(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1; // 表示未找到目标值
        }

        int mid = left + (right - left) / 2; // 防止溢出
        if (arr[mid] == target) {
            return mid; // 找到目标值，返回其索引
        } else if (arr[mid] < target) {
            return recursiveBinarySearchHelper(arr, target, mid + 1, right); // 在右半部分继续查找
        } else {
            return recursiveBinarySearchHelper(arr, target, left, mid - 1); // 在左半部分继续查找
        }
    }
}

二、非递归实现

public class BinarySearch {
    public static int iterativeBinarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出
            if (arr[mid] == target) {
                return mid; // 找到目标值，返回其索引
            } else if (arr[mid] < target) {
                left = mid + 1; // 在右半部分继续查找
            } else {
                right = mid - 1; // 在左半部分继续查找
            }
        }
        return -1; // 表示未找到目标值
    }
}

三、二分查找的优化版本

为了计算mid, 还可以 继续优化，我们将除以2这种操作转换为位运算mid=left+((right-left)>>1).

四、二分查找的变性

1、 查找第一个值等于给定值的情况

关键代码：

if (arr[mid] == target) {
    if(mid == 0 || arr[mid-1]!=target) {
        return mid; // 找到目标值，返回其索引
    } else {
        right = mid - 1;
    }
}

//二分查找变性，查找第一个值等于给定值的情况
public class BinarySearch1 {
    public static int iterativeBinarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出
            if (arr[mid] == target) {
                if(mid == 0 || arr[mid-1]!=target) {
                    return mid; // 找到目标值，返回其索引
                } else {
                    right = mid - 1;
                }
            } else if (arr[mid] < target) {
                left = mid + 1; // 在右半部分继续查找
            } else {
                right = mid - 1; // 在左半部分继续查找
            }
        }
        return -1; // 表示未找到目标值
    }

    public static void main(String[] argo) {
        int[] nums = new int[]{1,2,3,3,4,4,5,6,7};
        System.out.println(iterativeBinarySearch(nums, 4));//4
    }

}

2、 查找最后一个值等于给定值的情况

关键代码:

if (arr[mid] == target) {
    if(mid == (arr.length - 1) || arr[mid+1]!=target) {
        return mid; // 找到目标值，返回其索引
    } else {
        left = mid + 1;
    }
} 

//二分查找变性，查找最后一个值等于给定值的情况
public class BinarySearch2 {
    public static int iterativeBinarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出
            if (arr[mid] == target) {
                if(mid == (arr.length - 1) || arr[mid+1]!=target) {
                    return mid; // 找到目标值，返回其索引
                } else {
                    left = mid + 1;
                }
            } else if (arr[mid] < target) {
                left = mid + 1; // 在右半部分继续查找
            } else {
                right = mid - 1; // 在左半部分继续查找
            }
        }
        return -1; // 表示未找到目标值
    }

    public static void main(String[] argo) {
        int[] nums = new int[]{1,2,3,3,4,4,5,6,7};
        System.out.println(iterativeBinarySearch(nums, 4));//5
    }

}

3、查找第一个大于等于给定值的情况

分析思路

1 如果nums[mid]小于要查找的值，那么我们需要查找在[mid+1,right]之间，所以此时更新为left=mid+1

2 如果nums[mid]大于等于给定值value,这个时候需要查看nums[mid]是不是我们需要找的第一个值大于等于给定值元素，如果nums[mid]前面没有元素或者前面一个元素小于查找的值，那么nums[mid]就是我们需要查找的值。

//二分查找变性，查找第一个大于等于给定值的情况
public class BinarySearch3 {
    public static int iterativeBinarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出
            if (arr[mid] < target) {
                left = mid + 1; // 在右半部分继续查找
            } else if (arr[mid] >= target) {
                if(mid == 0 || arr[mid-1] < target){
                    return mid;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1; // 表示未找到目标值
    }

    public static void main(String[] argo) {
        int[] nums = new int[]{1,2,3,3,4,4,5,6,7};
        System.out.println(iterativeBinarySearch(nums, 3));//2
    }

}

思考继续变性：查找第一个大于给定值的情况，特殊考虑等于情况即可

4、查找最后一个小于等于给定值的情况

分析思路：

如果nums[mid]小于查找的值，那么需要查找的值肯定在[mid+1,right]之间，所以我们需要更新left=mid+1 2

如果nums[mid]大于等于给定的value，检查nums[mid]是不是我们的第一个值大于等于给定值的元素

//二分查找变性，查找最后一个小于等于给定值的情况
public class BinarySearch4 {
    public static int iterativeBinarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出
            if (arr[mid] > target) {
                    right = mid - 1; // 在左半部分继续查找
            } else if (arr[mid] <= target) {
                if(mid == arr.length - 1 || arr[mid+1] >target) {
                    return mid;
                } else {
                    left = mid + 1; // 在右半部分继续查找
                }
            }
        }
        return -1; // 表示未找到目标值
    }

    public static void main(String[] argo) {
        int[] nums = new int[]{1,2,3,3,4,4,5,6,7};
        System.out.println(iterativeBinarySearch(nums, 3));//3
    }

}

思考继续变性：查找最后一个小于给定值的情况，特殊考虑等于情况即可