LeetCode 704. 二分查找 题解

本题考查的就是一个基本的整数二分查找问题

对于整数二分，有单调性一定可以二分，没有单调性的有时候也可以二分。

算法思想（分为两种方法）：

1. 查找结果是在左边区间的情况
   区间被划分为[l,mid]和[mid+1,r]
   1、确定分界点，mid=q[(l+r)/2]
   2、判断是否满足
   是：区间变成[l,mid] 因此：r=mid
   否：区间变成[mid+1,r] 因此 l=mid+1

2. 查找结果在右边区间的情况
   区间被划分为[l,mid-1]和[mid,r]
   1、确定分界点，mid=q[(l+r+1)/2]
   2、判断是否满足
   是：区间变成[mid,r] 因此：l=mid
   否：区间变成[l,mid-1] 因此 r=mid-1
   两种方法都可以，那么如何选择呢？：
   先写check函数,当为check为真时，如果答案在mid左边，则不加1，答案在右边，则加1 （即右加左不加）
   mid一定是变到有答案的区间，即左边有答案则往左边变，不加1，右边有答案，往右边变，加1

以下是代码模板
方法一：

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}

方法二：

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

本题代码：

func search(nums []int, target int) int {

    left := 0 
    right := len(nums)-1
    res := -2
    for left < right {
        mid :=  (left + right ) / 2
        if nums[mid] >= target{
            right = mid
        }else {
            left = mid + 1
        }
    }
    if nums[left] != target {
        res = -1
    }else{
       res = left
    }
    return res
}