勇闯BAT 二分查找

水深无声 2023-01-22 04:55 82阅读 0赞

**方法名称：**

binarySearch（a，x）

**输入：**

*  a：有序数组
 *  x：目标值

**例如，我们将使用int \[\] \{11，88，99，111，223，999，1028\}**

![20210517161824190.png_pic_center][]

**输出：**

a \[i\] == x或-1（如果找不到）的索引位置

**程序：**

*  1.定义开始和范围变量

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FidTkzNTAwOTA2Ng_size_16_color_FFFFFF_t_70][]

*  2.将start设置为0，并将范围设置为a的长度/大小

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FidTkzNTAwOTA2Ng_size_16_color_FFFFFF_t_70 1][]

*  3.在start<=range时，请执行以下操作：
    
     *  定义一个中间变量并将其设置为（start + range）/ 2，这将获得中间元素

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RCzSmgdY-1621239440902)(C:\\Users\\86182\\AppData\\Local\\YNote\\data\\935009066@qq.com\\94aa773761b44b4ebac92c85b7d86fd3\\k9t9m7aebvuv.png)\]][img-RCzSmgdY-1621239440902_C_Users_86182_AppData_Local_YNote_data_935009066_qq.com_94aa773761b44b4ebac92c85b7d86fd3_k9t9m7aebvuv.png]

*  如果x> a \[mid\]，则将起始变量设置为mid + 1

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FidTkzNTAwOTA2Ng_size_16_color_FFFFFF_t_70 2][]

*  否则，如果x <a \[mid\]将范围变量设置为mid-1

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FidTkzNTAwOTA2Ng_size_16_color_FFFFFF_t_70 3][]

*  如果a \[mid\] = x，则返回mid
 *  **4.如果找不到该值，则返回-1**

代码示例：

public class MyClass { 
      public static void main(String[] args) { 
            System.out.print(binarySearch( new int[]{ 11, 88, 99, 111, 223, 999, 1028}, 999 ));
      }  
    
      public static int binarySearch(int[] a, int x){ 
        int start = 0;
        int range = a.length-1;
    
        while(start <= range){ 
            int mid = (start + range) / 2;
    
            if(x > a[mid]) start = mid + 1; 
            else if(x < a[mid]) range = mid - 1;
            else return mid;
        }
        return -1;
      }
    }

翻译：

*  https://dev.to/tommyc/binary-search-algorithm-4inp

[20210517161824190.png_pic_center]: /images/20221020/0d433c4f171b47e8a711f666f64a9537.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FidTkzNTAwOTA2Ng_size_16_color_FFFFFF_t_70]: /images/20221020/659aa36ae0904f48be3981b603b60789.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FidTkzNTAwOTA2Ng_size_16_color_FFFFFF_t_70 1]: /images/20221020/e982c4b4f005456d9feb411fbee99fb3.png
[img-RCzSmgdY-1621239440902_C_Users_86182_AppData_Local_YNote_data_935009066_qq.com_94aa773761b44b4ebac92c85b7d86fd3_k9t9m7aebvuv.png]: /images/20221020/4b98b4a54d984f269836ccb7001e1bc7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FidTkzNTAwOTA2Ng_size_16_color_FFFFFF_t_70 2]: /images/20221020/c61eaadc5f4242f186fd687429faeed8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FidTkzNTAwOTA2Ng_size_16_color_FFFFFF_t_70 3]: /images/20221020/3dcdb310ed3f467bad5a963debbb68d2.png