NC+LC：二分查找

有序不重复

NC160 二分查找-I

LC 704.二分查找：https://leetcode-cn.com/problems/binary-search/

题目描述

给定一个元素升序的、无重复数字的整型数组 $nums\$ 和一个目标值 $target\$ ，写一个函数搜索 $nums\$ 中的 $target\$ ，如果目标值存在返回下标（下标从 0 开始），否则返回 -1

要求：时间复杂度 $O(\log n)\$ ，空间复杂度 $O(1)$

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length == 0){
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target){ //等于直接返回
                return mid;
            }else if(nums[mid] < target){ //小于目标值说明目标值在右半部分，移动left
                left = mid + 1;
            }else{ 
                right = mid - 1; //大于目标值说明目标值在左半部分，移动right
            }
        }
        return -1;
    }
}

有序有重复

NC105 二分查找-II

题目描述

请实现有重复数字的升序数组的二分查找，也相当于查找第一个等于或大于的位置

示例

输入：[1,2,4,4,5],4 返回值：2
说明：从左到右，查找到第1个为4的，下标为2，返回2

思路

因为数组是有序的，所以相等值会聚集在一起，本题需要返回第一个出现的，即下标最小的，所以当查找到目标值时，就往前遍历是否还有相等值

实现代码1

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        if(nums.length == 0 || nums == null){
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = (left + right)/2;
            if(nums[mid] == target){
                //若前面还有重复数据，往前遍历返回下标最小的
                int k = mid - 1;
                while(k >= 0 && nums[mid] == nums[k]){
                    mid = k;
                    k--;
                }
                return mid;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }
}

实现代码2

在找到目标值之后，可以继续对目标值左边的元素进行二分查找，以此找到第一次出现的位置，比起在里面嵌套循环，这种方法代码更加简洁，运行速度也较快。

import java.util.*;

public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        // write code here
        int res = -1;
        int left = 0;
        int right = n - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(A[mid] == val){
                //将当前val的位置赋给res，有新的位置可进行更新
                res = mid;
                //继续对其左边进行查找，查找val第一次出现的位置
                right = mid - 1;
            }else if(A[mid] < val){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return res;
    }
}