Leetcode discuss: 34. Find First and Last Position of Element in Sorted Array

Here is the link.

C# binary search algorithm practice on June 26, 2020

June 26, 2020

Introduction

Algorithm mock interview has a few things for me to work on in short term. One is to have a correct idea to solve problem, another one is to test my own code carefully, before I submit the code; Next is how to fix the problem by observing failed test cases.

I need to work on two areas. First is to test my own code, really go over simple test case, read my own code, one line a time, one variable a time.

Second is to fix timeout error, mix variable names etc.

Those two areas brought my practice on June 26, 2020 to low level. I have to humble myself and then practice more.

Binary search
It is my most favorite algorithm. I failed so many times and I like to emphasize the testing, simple thing like reading my own code after the completion of the code.

Discuss and think about carefully. That is personality I should learn and work on.

My performance
I spent near one hour to code and fix the bugs. I even ran visual studio debugger for a few minutes.

public class Solution {
    public int[] SearchRange(int[] nums, int target) {
        if(nums == null || nums.Length == 0)
            return new int[]{-1,-1};
        
        var start = applyBinarySearchLeftmost(nums, target); 
        var end   = applyBinarySearchRightmost(nums, target); 
        
        return new int[]{start, end};
    }
    
    /// leftmost
    /// rightmost
    // [2, 2]
    private int applyBinarySearchLeftmost(int[] nums, int target)
    {
        // apply binary search
        var length = nums.Length;
        var start = 0; // 1
        var end = length - 1; //1
        while(start <= end) 
        {
            var middle = start + (end - start)/ 2; // 0
            var middleValue = nums[middle]; // 2
            var findTarget = middleValue == target;// 2
            if(findTarget)
            {
                if(middle == start || (middle == 0 || nums[middle - 1] != middleValue))
                {
                    return middle; // 0
                }
                else 
                {
                    end = middle - 1; 
                }
            }
            else if(target < middleValue)
            {
                end = middle - 1; 
            }
            else 
            {
                start = middle + 1; 
            }            
        }
        
        return -1; 
    }
    // [2, 2]
    // [1, 2, 3]
    private int applyBinarySearchRightmost(int[] nums, int target)
    {
        // apply binary search
        var length = nums.Length;
        var start = 0; 
        var end = length - 1; 
        while(start <= end) // 0, 0
        {
            var middle = start + (end - start)/ 2; // 0
            var middleValue = nums[middle]; //0 - [1, 2, 3], 1 return [0, 1], should be [0,0], not start
            var findTarget = middleValue == target; // true
            if(findTarget)
            {   
                if(middle == end || nums[middle + 1] != middleValue)  // change middle == length - 1 to middle == end
                {
                    return middle; // 0 
                }
                else 
                {
                    start = middle + 1; // caught by [2,2], 2 - time limit exceeded, start = middle + 1, not start = middle - 1;
                }
            }
            else if(target < middleValue)
            {
                end = middle - 1; // 0
            }
            else 
            {
                start = middle + 1; 
            }            
        }
        
        return -1; 
    }
}