欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

【二分查找算法】基本算法实现及应用

2026-02-08 分类：服务器技术 阅读(39) 评论(0)

一、二分查找算法

  1.1 算法概述

      在有序数组A中（升序排列），要查找的值为 target ，如果找到就返回索引，未找到返回-1。

  1.2 算法步骤

      1.设置两个指针 i 和 j –> i = 0 , j = arr.length – 1
      2.设置一个变量 m 作为中间值 –> m = (i + j) / 2
      3.将目标值 target 与中间值所对应的数据进行比较
      4.若 target < arr[m] , 就让 j = m – 1 –> 目标值在左半部分
      5.若 arr[m] < target , 就让 i = m + 1 –> 目标值在右半部分
      6.若 target = arr[m] , 就直接返回 m
      7.若循环结束还没找到 , 返回 -1

    注：m = (i + j) / 2 严格意义上来说是要向下取整 –> m = floor((i + j) / 2)

  1.3 代码实现

    1.3.1 算法代码

public int BinarySearch01(int[] arr, int target){
int i = 0, j = arr.length – 1;
while(i <= j){
int m = (i + j) / 2;
if(target < arr[m]){
j = m – 1;
}else if(arr[m] < target){
i = m + 1;
}else{
return m;
}
}
return -1;
}

    1.3.2 测试代码

import java.util.Scanner;

public static void main(String[] args){
BinarySearch bs = new BinarySearch();
Scanner sc = new Scanner(System.in);
System.out.print("请输入要查找的数字:");
int target = sc.nextInt();
int[] arr = {1,2,3,4,5,6,7,8,9,10};
int result = bs.BinarySearch01(arr,target);
System.out.println("下标为:" + result);
}

    1.3.3 运行结果

    上述代码有一个缺点就是在 m = (i + j) / 2 的时候，当数组长度非常大的时候，m有可能会超出机器能表示数的范围从而 m 出错得不到正确的结果，所以来用右移符号来表示。

    在二进制中，右移一位相当于 ÷2 ，右移 n 位相当于 ÷2^{n}，这样的话无论是带符号还是不带符号的数就都可以解决了。

    1.3.4 代码改进

public int BinarySearch01(int[] arr, int target){
int i = 0, j = arr.length – 1;
while(i <= j){
int m = (i + j) >>> 1;
if(target < arr[m]){
j = m – 1;
}else if(arr[m] < target){
i = m + 1;
}else{
return m;
}
}
return -1;
}

二、二分查找算法扩展

    当给定数组内有多个相同元素的情况下需要分是要返回最左边元素下标还是返回最右边元素下标

  2.1 查找相同元素中最左边元素位置

    2.1.1 初步思路

      总体上还是先实现二分查找在基础上进行改动，当第一次查找到目标值时不急于返回因为有可能还要继续向左查找。我们可以先把找到的数据下标定为一个候选值看看之后还需不需要更新，然后使j = m – 1，在继续查找，直到循环结束，那么返回的就是最终的下标值。

    2.1.2 具体步骤

         1.设置两个指针 i 和 j –> i = 0 , j = arr.length – 1
         2.设置一个变量 m 作为中间值 –> m = (i + j) >>> 1
         3.设置一个变量 targets 作为候选值，targets = -1
         4.将目标值 target 与中间值所对应的数据进行比较
         5.若 target < arr[m] , 就让 j = m – 1 –> 目标值在左半部分
         6.若 arr[m] < target , 就让 i = m + 1 –> 目标值在右半部分
         7.若 target = arr[m] , 更新 targets –> targets = m，j = m – 1，回到 4 继续知道循环结束

    2.1.3 图形解释

    2.1.4 代码实现

public int LeftMost(int arr[], int target){
int i = 0, j = arr.length – 1;
int targets = -1;
while(i <= j){
int m = (i + j) >>> 1;
if(target < arr[m]){
j = m – 1;
}else if(arr[m] < target){
i = m + 1;
}else{
targets = m;
j = m – 1;
}
}
return targets;
}

    2.1.5 测试代码

import java.util.Scanner;

public static void main(String[] args){
BinarySearch bs = new BinarySearch();
Scanner sc = new Scanner(System.in);
System.out.print("请输入要查找的数字:");
int target = sc.nextInt();
int[] arr = {1,2,3,5,5,5,5,8,9,10};
int result = bs.LeftMost(arr,target);
System.out.println("下标为:" + result);
}

    2.1.6 运行结果

    2.1.7 代码改进

    我们发现上述代码中 j = m – 1 出现在了两个判断中，是否能合并一下使代码更简洁一些。

    是可以的，我们直接去掉候选值 targets，把 target < arr[m] 和 target = arr[m] 合并成 target <= arr[m]，最后的返回值直接返回 i 就可以了！

    i 表示的是：返回 >= target的最靠左索引

    2.1.8 改后代码

public int LeftMost(int arr[], int target){
int i = 0, j = arr.length – 1;
while(i <= j){
int m = (i + j) >>> 1;
if(target <= arr[m]){
j = m – 1;
}else {
i = m + 1;
}
}
return i;
}

    2.1.9 测试代码

import java.util.Scanner;

public static void main(String[] args){
BinarySearch bs = new BinarySearch();
Scanner sc = new Scanner(System.in);
System.out.print("请输入要查找的数字:");
int target = sc.nextInt();
int[] arr = {1,2,3,3,5,5,5,8,9,10};
int result = bs.LeftMost(arr,target);
System.out.println("下标为:" + result);
}

    2.1.10 运行结果

  2.2 查找相同元素中最右边元素位置

    和上面思路大部分一致，只是这次是向右查找，需要改变 i 的值 –> i = m + 1，还有最终返回值为 i – 1（表示返回的是 <=target 的最靠右索引值），就直接放代码和测试结果了。

    为什么最终返回值是 i – 1 ？是因为当我们查找完之后退出循环的时候，这时候需要满足 i > j 的情况下才能退出循环，此时 i 的位置在最右目标值的右边（因为 i = j 的时候还要循环一次，i 进行 i + 1，之后才跳出循环），所以我们要对 i 进行 i – 1 才是我们最终要的结果！

    2.2.1 基础版代码

public int RightMost(int arr[], int target){
int i = 0, j = arr.length – 1;
int targets = -1;
while(i <= j){
int m = (i + j) >>> 1;
if(target < arr[m]){
j = m – 1;
}else if(arr[m] < target){
i = m + 1;
}else{
targets = m;
i = m + 1;
}
}
return targets;
}

    2.2.2 改进版代码

public int RightMost(int arr[], int target){
int i = 0, j = arr.length – 1;
while(i <= j){
int m = (i + j) >>> 1;
if(target < arr[m]){
j = m – 1;
}else {
i = m + 1;
}
}
return i – 1;
}

    2.2.3 测试代码

import java.util.Scanner;

public static void main(String[] args){
BinarySearch bs = new BinarySearch();
Scanner sc = new Scanner(System.in);
System.out.print("请输入要查找的数字:");
int target = sc.nextInt();
int[] arr = {1,2,3,3,5,5,5,8,9,10};
int result = bs.RightMost(arr,target);
System.out.println("下标为:" + result);
}

    2.2.4 运行结果

三、二分查找算法的应用

  3.1 求排名

    3.1.1 思路及步骤

        思路：最终是求目标值在数组中是第几位，求出索引再将索引 +1 就可以了

        步骤：1.用上面查找相同元素中最左边的元素方法得到下标值

                   2.将下标值进行 +1 操作

    3.1.2 代码实现

public int Rank(int arr[], int target){
int i = 0, j = arr.length – 1;
while(i <= j){
int m = (i + j) >>> 1;
if(target <= arr[m]){
j = m – 1;
}else {
i = m + 1;
}
}
return i + 1;
}

    3.1.3 测试代码

import java.util.Scanner;

public static void main(String[] args){
BinarySearch bs = new BinarySearch();
Scanner sc = new Scanner(System.in);
System.out.print("想看哪个数字的排名:");
int target = sc.nextInt();
int[] arr = {1,2,3,4,5,6,7,8,9,10};
int result = bs.Rank(arr,target);
System.out.println(target + "的排名为:" + result);
}

    3.1.4 运行结果

  3.2 求前驱

    3.2.1 思路及步骤

       思路：先拿到目标值的下标，再将下标 -1 就好了，要考虑到有重复元素的情况，需要找出最                    左边元素位置再进行 -1

       步骤：1.用上面查找相同元素中最左边的元素方法得到下标值

                  2.将下标值进行 -1 操作

    3.2.2 代码实现

public int Predecessor(int arr[], int target){
int i = 0, j = arr.length – 1;
while(i <= j){
int m = (i + j) >>> 1;
if(target <= arr[m]){
j = m – 1;
}else {
i = m + 1;
}
}
return arr[i – 1];
}

    3.2.3 测试代码

import java.util.Scanner;

public static void main(String[] args){
BinarySearch bs = new BinarySearch();
Scanner sc = new Scanner(System.in);
System.out.print("想看哪个数字的前驱:");
int target = sc.nextInt();
int[] arr = {1,1,3,4,5,5,5,8,9,10};
int result = bs.Predecessor(arr,target);
System.out.println(target + "的前驱为:" + result);
}

    3.2.4 运行结果

  3.3 求后继

    3.3.1 思路及步骤

       思路：先拿到目标值的下标，再将下标 +1 就好了，当然也要考虑到有重复元素的情况，需要                    找出最右边元素位置再进行 +1

       步骤：1.用上面查找相同元素中最右边的元素方法得到下标值

                  2.将下标值进行 +1 操作

    3.3.2 代码实现

public int Successor(int arr[], int target){
int i = 0, j = arr.length – 1;
while(i <= j){
int m = (i + j) >>> 1;
if(target < arr[m]){
j = m – 1;
}else {
i = m + 1;
}
}
return arr[i];

    3.3.3 测试代码

import java.util.Scanner;

public static void main(String[] args){
BinarySearch bs = new BinarySearch();
Scanner sc = new Scanner(System.in);
System.out.print("想看哪个数字的后继:");
int target = sc.nextInt();
int[] arr = {1,1,3,4,5,5,5,8,9,10};
int result = bs.Successor(arr,target);
System.out.println(target + "的后继为:" + result);
}

    3.3.4 运行结果

  3.4 求最近邻居

最近邻居：数组中与目标值差值最小的元素

    3.4.1 思路及步骤

      思路：先拿到目标值前一位和后一位的的数据，之后分别算出与目标值的差值，谁的差值的绝                   对值最小谁就是最近邻居，如果目标值在头或者尾，就直接返回目标值

      步骤： 1.对数据进行判断是否在头尾，若在直接返回

                  2.如果目标值 target 在数组中，找到并返回 target

                  3.如果目标值 target 不在数组中，就找出它的前驱和后继，并与 target 进行差值比较,                       差值绝对值最小的就是最近邻居

      如果差值一样的话我这里是返回的它的后继，比较大的那一个

    3.4.2 代码实现

public int NearestNeighbor(int arr[], int target){
if(target <= arr[0]){
return arr[0];
}
if(arr[arr.length – 1] <= target){
return arr[arr.length – 1];
}
int i = 0, j = arr.length – 1;
while(i <= j){
int m = (i + j) >>> 1;
if(target < arr[m]){
j = m – 1;
}else if(arr[m] < target){
i = m + 1;
}else{
return arr[m];
}
}
int left = Math.abs(arr[i] – target);
int right = Math.abs(arr[j] – target);
return left <= right ? arr[i] : arr[j];
}

    3.4.3 测试代码

public static void main(String[] args){
BinarySearch bs = new BinarySearch();
Scanner sc = new Scanner(System.in);
System.out.print("想看哪个数字的最近邻居:");
int target = sc.nextInt();
int[] arr = {1,3,7,10,11,13,17,18,19,22};
int result = bs.NearestNeighbor(arr,target);
System.out.println(target + "的最近邻居为:" + result);
}

    3.4.4 运行结果

  3.5 查找划定范围内的数

    3.5.1 小于目标值的数

       3.5.1.1 思路及步骤

          思路：找到目标值或多个重复目标值最左侧元素位置，把之前的数据移下来，可以用集合来                       存储

          步骤：1.找到目标值或多个重复目标值最左侧元素位置

                     2.创建一个空的集合

                     3.将0索引到最左侧索引-1的数据加入到集合中

       3.5.1.2 代码实现

public ArrayList<Integer> Range(int arr[], int target){
int i = 0, j = arr.length – 1;
ArrayList<Integer> list = new ArrayList<>();
while(i <= j){
int m = (i + j) >>> 1;
if(target <= arr[m]){
j = m – 1;
}else{
i = m + 1;
}
}
for(int a = 0; a < i; a++){
list.add(arr[a]);
}
return list;
}

       3.5.1.3 测试代码

import java.util.ArrayList;
import java.util.Scanner;

public static void main(String[] args){
BinarySearch bs = new BinarySearch();
Scanner sc = new Scanner(System.in);
System.out.print("目标值:");
int target = sc.nextInt();
int[] arr = {1,3,7,10,11,13,17,18,19,22};
ArrayList<Integer> result = bs.Range(arr,target);
System.out.println("小于目标值的值有:" + result);
}

       3.5.1.4 运行结果

    3.5.2 小于等于目标值的数

       3.5.2.1 思路及步骤

          思路：找到目标值或多个重复目标值最右侧元素位置，把之前的数据移下来，可以用集合来                       存储

          步骤：1.找到目标值或多个重复目标值最右侧元素位置

                     2.创建一个空的集合

                     3.将0索引到最右侧索引的数据加入到集合中

       3.5.2.2 代码实现

public ArrayList<Integer> Range(int arr[], int target){
int i = 0, j = arr.length – 1;
ArrayList<Integer> list = new ArrayList<>();
while(i <= j){
int m = (i + j) >>> 1;
if(target < arr[m]){
j = m – 1;
}else{
i = m + 1;
}
}
for(int a = 0; a <= i – 1; a++){
list.add(arr[a]);
}
return list;
}

       3.5.2.3 测试代码

import java.util.ArrayList;
import java.util.Scanner;

public static void main(String[] args){
BinarySearch bs = new BinarySearch();
Scanner sc = new Scanner(System.in);
System.out.print("目标值:");
int target = sc.nextInt();
int[] arr = {1,3,7,10,11,11,11,18,19,22};
ArrayList<Integer> result = bs.Range(arr,target);
System.out.println("小于等于" + target + "的数有:" + result);
}

       3.5.2.4 运行结果

    3.5.3 大于目标值的数

       3.5.3.1 思路及步骤

          思路：找到目标值或多个重复目标值最右侧元素位置，把之前的数据移下来，可以用集合来                       存储

          步骤：1.找到目标值或多个重复目标值最右侧元素位置

                     2.创建一个空的集合

                     3.将0索引到最右侧索引+1的数据加入到集合中

       3.5.3.2 代码实现

public ArrayList<Integer> Range(int arr[], int target){
int i = 0, j = arr.length – 1;
ArrayList<Integer> list = new ArrayList<>();
while(i <= j){
int m = (i + j) >>> 1;
if(target < arr[m]){
j = m – 1;
}else{
i = m + 1;
}
}
for(int a = i; a < arr.length; a++){
list.add(arr[a]);
}
return list;
}

       3.5.3.3 测试代码

import java.util.ArrayList;
import java.util.Scanner;

public static void main(String[] args){
BinarySearch bs = new BinarySearch();
Scanner sc = new Scanner(System.in);
System.out.print("目标值:");
int target = sc.nextInt();
int[] arr = {1,3,7,10,11,11,11,18,19,22};
ArrayList<Integer> result = bs.Range(arr,target);
System.out.println("大于" + target + "的数有:" + result);
}

       3.5.3.4 运行结果

    3.5.4 大于等于目标值的数

       3.5.4.1 思路及步骤

          思路：找到目标值或多个重复目标值最左侧元素位置，把之前的数据移下来，可以用集合来                       存储

          步骤：1.找到目标值或多个重复目标值最左侧元素位置

                     2.创建一个空的集合

                     3.将0索引到最左侧索引的数据加入到集合中

       3.5.4.2 代码实现

public ArrayList<Integer> Range(int arr[], int target){
int i = 0, j = arr.length – 1;
ArrayList<Integer> list = new ArrayList<>();
while(i <= j){
int m = (i + j) >>> 1;
if(target <= arr[m]){
j = m – 1;
}else{
i = m + 1;
}
}
for(int a = i; a < arr.length; a++){
list.add(arr[a]);
}
return list;
}

       3.5.4.3 测试代码

import java.util.ArrayList;
import java.util.Scanner;

public static void main(String[] args){
BinarySearch bs = new BinarySearch();
Scanner sc = new Scanner(System.in);
System.out.print("目标值:");
int target = sc.nextInt();
int[] arr = {1,3,7,10,11,11,11,18,19,22};
ArrayList<Integer> result = bs.Range(arr,target);
System.out.println("大于" + target + "的数有:" + result);
}

       3.5.4.4 运行结果

    3.5.5 目标值大于一个数和小于一个数之间的数

       3.5.5.1 思路及步骤

           思路：找到起始值或多个重复起始值的最右侧索引值和终点值或多个重复终点值的最左侧                          索引值，取出它们之间的数

          步骤：1.找到起始值或多个重复起始值的最右侧索引值和终点值或多个重复终点值的最左侧                       索引值

                     2.创建一个空的集合

                     3.将起始值或多个重复起始值的最右侧索引值+1到终点值或多个重复终点值的最左侧                          索引值-1的数据加入到集合中

       3.5.5.2 代码实现

public ArrayList<Integer> Range(int arr[], int left, int right){
int i = 0, j = arr.length – 1;
ArrayList<Integer> list = new ArrayList<>();
while(i <= j){
int m = (i + j) >>> 1;
if(left < arr[m]){
j = m – 1;
}else{
i = m + 1;
}
}
int c = 0, b = arr.length – 1;
while(c <= b){
int n = (c + b) >>> 1;
if(right <= arr[n]){
b = n – 1;
}else{
c = n + 1;
}
}
for(int a = i; a < c; a++){
list.add(arr[a]);
}
return list;
}

       3.5.5.3 测试代码

import java.util.ArrayList;
import java.util.Scanner;

public static void main(String[] args){
BinarySearch bs = new BinarySearch();
Scanner sc = new Scanner(System.in);
System.out.print("起始值:");
int left = sc.nextInt();
System.out.print("终点值:");
int right = sc.nextInt();
int[] arr = {1,3,7,10,11,11,11,18,19,22};
ArrayList<Integer> result = bs.Range(arr,left,right);
System.out.println("大于" + left + "小于" + right + "的数有:" + result);
}

       3.5.5.4 运行结果

    3.5.6 目标值大于等于一个数和小于等于一个数之间的数

       3.5.6.1 思路及步骤

          思路：找到起始值或多个重复起始值的最左侧索引值和终点值或多个重复终点值的最右侧索                       引值，取出它们之间的数

          步骤：1.找到起始值或多个重复起始值的最左侧索引值和终点值或多个重复终点值的最右侧                          索引值

                     2.创建一个空的集合

                     3.将起始值或多个重复起始值的最左侧索引值到终点值或多个重复终点值的最右侧索                       引值的数据加入到集合中

       3.5.6.2 代码实现

public ArrayList<Integer> Range(int arr[], int left, int right){
int i = 0, j = arr.length – 1;
ArrayList<Integer> list = new ArrayList<>();
while(i <= j){
int m = (i + j) >>> 1;
if(left <= arr[m]){
j = m – 1;
}else{
i = m + 1;
}
}
int c = 0, b = arr.length – 1;
while(c <= b){
int n = (c + b) >>> 1;
if(right < arr[n]){
b = n – 1;
}else{
c = n + 1;
}
}
for(int a = i; a < c; a++){
list.add(arr[a]);
}
return list;
}

       3.5.6.3 测试代码

import java.util.ArrayList;
import java.util.Scanner;

public static void main(String[] args){
BinarySearch bs = new BinarySearch();
Scanner sc = new Scanner(System.in);
System.out.print("起始值:");
int left = sc.nextInt();
System.out.print("终点值:");
int right = sc.nextInt();
int[] arr = {1,3,7,10,11,11,11,18,19,22};
ArrayList<Integer> result = bs.Range(arr,left,right);
System.out.println("大于等于" + left + "小于等于" + right + "的数有:" + result);
}

       3.5.6.4 运行结果

四、总结

    这些主要是对二分查找算法的认识，也让我收获了很多。让我知道了很多解法是类似的只需要稍微变动一下就好，代码是自己写的，可能有的地方有些繁琐或者是有些情况没有多家分析的小问题，写的是核心代码。希望对有需要的人有帮助，欢迎大家积极讨论，谢谢观看！

赞(0)
未经允许不得转载：171主机测评 » 【二分查找算法】基本算法实现及应用
分享到： 更多 (0)
标签：

相关推荐

评论 抢沙发

取消

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

热门标签

#人工智能(59166)#python(20075)#开发语言(16837)#java(15450)#运维(15338)#linux(14931)#大数据(14559)#服务器(13049)#算法(11761)#前端(10890)#网络(9357)#ai(8894)#数据库(8886)#c++(8158)#课程设计(6798)#学习(6757)#机器学习(6701)#区块链(5917)#OpenClaw(5388)#后端(5144)#spring boot(5001)#深度学习(4941)#c语言(4373)#毕业设计(4293)#数据结构(4191)#安全(4053)#docker(3926)#架构(3848)#javascript(3803)#大模型(3647)

热门文章

最新文章

归档

分类