二分查找

二分查找要实现查找，主要是要保证 循环不变量原则；

题目

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

根据循环不变量的原则，二分查找可以分为两种写法；

代码

Java代码（左闭右开）

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while(left < right){
            int mid = (right - left) /2 + left;
            if(target < nums[mid]){
                right = mid;
            }else if(target > nums[mid]){
                left = mid +1;
            }else {
                return mid;
            }
        }
        return -1;
    }
}

方法一：左闭右开

include <iostream>
include <vector>
using namespace std;

class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        // 区间原则：左闭右开
        int low = 0;
        int high = nums.size();
        for (; low < high;)
        {
            // 防止溢出
            int mid = low + (high - low) / 2;
            if (target < nums[mid])
            {
                high = mid;
            }
            else if (nums[mid] < target)
            {
                low = mid + 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
};

int main()
{
    Solution s;
    vector<int> test1 = {1, 0, 3, 5, 9, 12};
    vector<int> test2 = {1, 0, 3, 5, 9, 12};
    cout << "test1 :" << s.search(test1, 9) << endl;
    cout << "test2 :" << s.search(test2, 2) << endl;
}

方法二：左闭右闭

include <iostream>
include <vector>
using namespace std;

class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        int low = 0;
        // 右闭定义：
        int high = nums.size() - 1;
        while (low <= high)
        {
            int mid = low + (high - low) / 2;
            if (target < nums[mid])
            {
                high = mid - 1;
            }
            else if (nums[mid] < target)
            {
                low = mid + 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
};

int main()
{
    Solution s;
    vector<int> test1 = {1, 0, 3, 5, 9, 12};
    vector<int> test2 = {1, 0, 3, 5, 9, 12};
    cout << "test1 :" << s.search(test1, 9) << endl;
    cout << "test2 :" << s.search(test2, 2) << endl;
}