二分查找左邊界問題

題目描述

請實作有重複數字的有序數組的二分查找。

輸出在數組中第一個大于等于查找值的位置，如果數組中不存在這樣的數，則輸出數組長度加一。

示例1

輸入

5,4,[1,2,4,4,5]
           

輸出

3
           

import java.util.*;


public class Solution {
    /**
     * 二分查找
     * @param n int整型 數組長度
     * @param v int整型 查找值
     * @param a int整型一維數組 有序數組
     * @return int整型
     */
    public int upper_bound_ (int n, int v, int[] a) {
        // write code here
        return findLeft(a,v,0,n-1);
    }
    
    //二分查找左邊界
    public int findLeft(int[] array,int target,int start,int end){
        
        while(start <= end){
            //防止start+end越界超出int範圍
            int mid = start + (end - start)/2;

            if(array[mid] == target){
                end = mid -1;
            }else if(array[mid] > target){
                end = mid - 1;
            }else if(array[mid] < target){
                start = mid + 1;
            }
        }
        
        /**
          *理論上應該是 if(start >= array.length || array[start] != target)
          *但是題目要求的是輸出在數組中第一個大于等于查找值的位置
          *是以這裡換成array[start] < target)
          *
        */
        if(start >= array.length || array[start] < target){
            //如果數組中不存在這樣的數，則輸出數組長度加一
            return array.length + 1;
        }
        
        //按照題目示例 應該是下标+1
        return start+1;
    }

    
}
           

import java.util.*;


public class Solution {
    /**
     * 二分查找
     * @param n int整型 數組長度
     * @param v int整型 查找值
     * @param a int整型一維數組 有序數組
     * @return int整型
     */
    public int upper_bound_ (int n, int v, int[] a) {
        int result = leftBound(n,v,a);
        return result;
    }
    
    
    //二分查找左邊界
    public int leftBound(int n,int target, int[] a){
        
        int leftIndex = 0;
        int rightIndex = n-1;
        
        while(leftIndex <= rightIndex){
            int mid = leftIndex + (rightIndex - leftIndex)/2;
            if(target == a[mid]){
                rightIndex = mid - 1;
            }else if(target > a[mid]){
                leftIndex = mid + 1;
            }else if(target < a[mid]){
                rightIndex = mid - 1;
            }
        }
        
        //a[leftIndex] != target 這樣寫是代表 如果數組是1,2,3 target=0 那麼這裡輸出101
        //但題目是要求 第一感大于等于target的 是以當不存在時,輸出數組元素1的index
        //是以這裡應該改為a[leftIndex] < target 才代表不存在大于等于target的值
        //if(leftIndex >= a.length || a[leftIndex] != target){
        if(leftIndex >= a.length || a[leftIndex] < target){
            return a.length + 1;
        }
        
        //按照題目來看 應該是數組下标+1
        return leftIndex + 1;
    }
}
           

測試資料:

public static void main(String[] args) {
        int[] a = {2,3,4,4,4,7,7,8,10,10,11,12,13,14,15,15,17,18,19,23,24,24,24,24,25,26,26,26,27,27,28,29,29,30,33,36,38,38,40,40,41,43,43,43,44,46,46,47,51,52,52,53,54,56,57,57,57,58,58,61,61,61,62,64,64,66,66,67,67,67,70,72,74,74,74,75,75,78,78,78,79,79,80,83,83,83,83,84,84,86,88,89,89,90,91,91,92,93,93,96};
        int k = leftBound(100,1,a);
        System.out.println(k);
    }