二分查找前提条件

  • 数组是有序的
  • 数组中没有重复的元素

二分方法一般有两种写法

一 左闭右闭

当左大于右时，整体结束。
如果左小于等于右则继续查找。
每次mid =左加（(右减左)/2）除2操作也可以看做时右移一位
如果mid 值为目标则返回
否则mid 值大于目标让右等于mid+1
否则mid 小于目标让左等于mid+1

二左闭右开

当左大于等于右时循环结束
如果左小于右则继续查找
每次mid=左加（(右减左)/2）除2操作也可以看做时右移一位
如果mid 值为目标则返回
否则mid 值大于目标让右等于mid
否则mid 小于目标让左等于mid+1

时间复杂度与空间复杂度

二分查找的方法时间复杂度为o(logn)因为一直除2的操作，假如查找了k次，那么2^k为n
空间复杂为o(1).

Leetcode 35题

在这里插入图片描述

写法1

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
28
29
30
class Solution {
    
    public int searchInsert(int[] nums, int target) {
    
        int left=0;
        int right=nums.length-1;
        int mid=0;
        boolean flag=true;
        while(left<=right){
    
            mid=left+((right-left)>>1);
            if(nums[mid]==target){
    
                return mid;
            }else if(nums[mid]<target){
    
                flag=true;
                left=mid+1;
            }else{
    
                flag=false;
                right=mid-1;
            }
        }
        if(flag)
            return left;
        else  
            return right+1;
    }
}

写法2

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
class Solution {
    
    public int searchInsert(int[] nums, int target) {
    
        int left=0;
        int right=nums.length;
        int mid=0;
        while(left<right){
    
            mid=left+((right-left)>>1);
            if(nums[mid]==target){
    
                return mid;
            }else if(nums[mid]<target){
    
                left=mid+1;
            }else{
    
                right=mid;
            }
        }
        
        return right;
    }
}