【算法】查找算法

墨蓝 2024-03-16 10:21 48阅读 0赞

#### 文章目录 ####

*  二分查找并返回数据应该插入的位置

## 二分查找并返回数据应该插入的位置 ##

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

public static int searchInsert(int[] nums, int target) {
        
            int low = 0;
            int high = nums.length-1;
            while(low<=high){
        
                int mid = (low+high)>>>1;
                if(nums[mid]<target){
        
                    low = mid+1;
                }else if(target<nums[mid]){
        
                    high = mid - 1;
                }else{
        
                    return mid;
                }
            }
            return low;
        }
        // ---------这种解法和上面那种差不多-------------
        //  public static int searchInsert(int[] nums, int target) {
        
        //     int low = 0;
        //     int high = nums.length-1;
        //     while(low<=high){
        
        //         int mid = (low+high)>>>1;
        //         if(target<=nums[mid]){
        
        //             high = mid -1 ; 
        //         }else{
        
        //             low = mid + 1;
        //         }
        //     } 
        //     return low;
        // }
    
    
        //-----------------解法--------------------
        // public static int searchInsert(int[] nums, int target) {
        
        //     int len = nums.length;
        //     if (nums[0] >= target) {
        
        //         return 0;
        //     }
        //     if (target == nums[len - 1]) {
        
        //         return len - 1;
        //     }
        //     if (target > nums[len - 1]) {
        
        //         return len ;
        //     }
        //     return binarySearch(nums, 0, len, target);
        // }
    
        // public static int binarySearch(int[] nums, int left, int right, int target) {
        
        //     while (left <= right) {
        
        //         int mid = (left + right) / 2;
        //         if (nums[mid] == target) {
        
        //             return mid;
        //         } else if (nums[mid] < target) {
        
        //             if (nums[mid + 1] > target) {
        
        //                 return mid+1;
        //             }
        //             return binarySearch(nums, mid, right, target);
        //         } else { //nums[mid]>target
        //             if (nums[mid - 1] < target) {
        
                        
        //                 return mid;
        //             }
        //             return binarySearch(nums, left, mid, target);
        //         }
        //     }
        //     return 0;
        // }