NC160 二分查找-I和NC105 二分查找-II

桃扇骨 2022-09-16 08:41 125阅读 0赞

两个都是按升序排好的数组，区别在于NC105可能会有重复，需要找出的是target第一次出现时的index，只需要第一次找到以后再继续往左找即可。

## NC160 二分查找-I ##

import java.util.*;
    
    
    public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param nums int整型一维数组 
         * @param target int整型 
         * @return int整型
         */
        public int search (int[] nums, int target) {
        
            // write code here
            int index=-1;
            int low=0;
            int high=nums.length-1;
            int mid=(low+high)/2;
            while(low<=high){
        
                mid=(low+high)/2;
                if(target>nums[mid]){
        
                    low=mid+1;               
                }else if(target<nums[mid]){
        
                    high=mid-1;
                }else if(target==nums[mid]){
        
                    index=mid;    
                    break;
                }
            }
            return index;
        }
    }

## NC105 二分查找-II ##

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
            int index=-1;
            int low=0;
            int high=nums.length-1;
            int mid=(low+high)/2;
            while(low<=high){
        
                mid=(low+high)/2;
                if(target>nums[mid]){
        
                    low=mid+1; // 往右找
                    
                }else if(target<nums[mid]){
        
                    high=mid-1;  // 往左找
    
                }else if(target==nums[mid]){
        
                    index=mid;  // 找到了 更新index
                    high=mid-1; // 继续往左找 看看还有没有符合条件的target
    
                }
            }
            return index;
        }
    }