Six different Binary Search approachs for your reference


  • 0
    L

    This is the Code:

    class Solution {
    public:
    // Open range, 3-way
    int search1(int A[], int n, int target) {
        int start = -1;
        int end = n;
        
        while (end - start > 1) {
            int mid = start + (end - start) / 2;
            
            if (target == A[mid]) return mid;
            if (target < A[mid]) end = mid;
            else start = mid;
        }
        
        return end;
    }
    
    // Open range, 2-way, find last appear
    int search2(int A[], int n, int target) {
        int start = -1;
        int end = n;
        
        while (end - start > 1) {
            int mid = start + (end - start) / 2;
            
            // A[start] < target <= A[end]
            if (A[mid] >= target) end = mid;
            else start = mid;
        }
        
        return end;
    }
    
    // open-range, 2-way, find first appear
    int search3(int A[], int n, int target) {
        int start = -1;
        int end = n;
        
        while (end - start > 1) {
            int mid = start + (end - start) / 2;
            
            // A[start] <= target < A[end]
            if (A[mid] <= target) start = mid;
            else end = mid;
        }
        
        if (start < 0 || A[start] != target) return end;
        else return start;
    }
    
    // colsed-range, 3-way
    int search4(int A[], int n, int target) {
        int start = 0;
        int end = n - 1;
        
        while (end >= start) {
            int mid = start + (end - start) / 2;
            
            if (target == A[mid]) return mid;
            if (A[mid] < target) start = mid + 1;
            else end = mid - 1;
        }
        
        return start;
    }
    
    // colsed-range, 2-way, find last appear
    int search5(int A[], int n, int target) {
        int start = 0;
        int end = n - 1;
        
        while (end >= start) {
            int mid = start + (end - start) / 2;
            
            // A[start] < target <= A[end]
            if (A[mid] >= target) end = mid - 1; 
            else start = mid + 1;
        }
        
        return start;
    }
    
    // colsed-range, 2-way, find first appear
    int search6(int A[], int n, int target) {
        int start = 0;
        int end = n - 1;
        
        while (end >= start) {
            int mid = start + (end - start) / 2;
            
            // A[start] <= target < A[end]
            if (A[mid] > target) end = mid - 1;
            else start = mid + 1;
        }
        
        if (end < 0 || A[end] != target) return start;
        else return end;
    }
    
    int searchInsert(int A[], int n, int target) {
        int method1 = search1(A, n ,target);
        int method2 = search2(A, n ,target);
        int method3 = search3(A, n ,target);
        int method4 = search4(A, n ,target);
        int method5 = search5(A, n ,target);
        int method6 = search6(A, n ,target);
        
        if (method1 != method2 || method1 != method3 || method1 != method4 ||
            method1 != method5 || method1 != method6)
            return -1;
            
        else return method1;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.