在数组中二分查找指定的数----时间复杂度O（log N）Java解法

二分查找----时间复杂度$O(logN)$

题目描述
给定15个按从大到小已经有序的整数，将其放在一个数组中。另外输入一个整数，要求使用折半查找法找出该数是数组中的第几个元素的值。如果该数不在数组中，则输出“NO”。
输入
第一行有15个整数，即15个从大到小已有序的原始整数。
第二行有一个整数，表示需要使用折半查找法查找的元素。
输出
如果查找到了输入的整数，则输出此数在序列中的序号，即第一个是0，最后一个是14。
如果查找不到这个整数，则输出“NO”。
请注意不需要输出引号，并请注意行尾输出换行。
样例输入
1 3 5 7 9 10 13 15 16 17 20 21 22 23 24
10
样例输出
5

JAVA代码：

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        int []arr = new int[15];
        for (int i = 0; i < 15; i++){
            arr[i] = cin.nextInt();
        }
        int x = cin.nextInt();
        int left = 0, right = 14;
        while (right - left >= 1){
            int mid = (left+right)>>1;
            if(x <= arr[mid]){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        if(arr[left] != x){
            System.out.println("NO");
        }
        else {
            System.out.println(left);
        }
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
 

总结：

下面这段代码是二分的核心部分，我的目的是将区间缩成长度为1，即最后只锁定一个数，如果这个数是等于x，那就找到了答案，否则就找不到，所以1处while循环的条件是right-left>=1,也可以写成left != right。2处是求中点，通过移位运算得到的中点总是偏左侧的数，我习惯这样写了。 重点来了，就是下面的if条件分支，我感觉这里极容易出错，会有可能出现死循环，如果想绕开这个坑，要让区间往右侧走，那就是mid的赋值和闭区间不能同时出现在统一分支，否则当区间长度为2时会区间不会更新，一直得到上一轮的区间值，也就是不可以写成if(x < arr[mid]){ right = mid-1; }else{ left = mid; }

int left = 0, right = 14;
while (right - left >= 1){ //1
     int mid = (left+right)>>1;//2
     if(x <= arr[mid]){// 3
         right = mid;//4
     }else{
         left = mid+1;//5
     }
 }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/85104686