Share my O(logN) code via binary search


  • 0
    C

    add some comments even though it is pretty straight forward.

    public class Solution {
    public int searchInsert(int[] A, int target) {
    if (A == null || A.length == 0) {
    return 0;
    }
    int start = 0, end = A.length - 1;
    while (start <= end) {
    int mid = (start + end) / 2;

            // if target is found, simply return its index
            if (A[mid] == target) {
                return mid;
                
            }
            if (A[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        
        // when start > end, which means target is not in array, 
        // we should return the index target should be in. 
        // Since we know the target must be in {A[end], target, A[start]},
        // the index value equals start.
        return start;
    }
    

    }


  • -1
    W

    I think you should notice about your format, as it is hard and not beautiful to see.
    And then, some suggestions. I think it's better to consider about the edge situation to make the algorithm more stronger.
    For example, the target is bigger than the last element or is smaler than the first one.
    Here is my code to make a communication:

    int searchInsert(int A[], int n, int target) {
            int first = 0, last = n - 1;
            if (A[first] > target){
                return first;
            }
            if (A[last] < target){
                return last + 1;
            }
            while (first <= last){
                int mid = (first + last) / 2;
                if (A[mid] < target){
                    first = mid + 1;
                }
                else if (A[mid] > target){
                    last = mid - 1;
                }
                else{
                    first = mid;
                    break;
                }
            }
            return first;
    
        }

  • 0
    C

    Thank you for notifying me of the format, @Bluefeather:)
    Also, my algorithm has considered the edge case. For target less than first element, such as given ({1, 2}, 0), program will return 0. For target greater than last element, you can put ({1, 2}, 3) into my algorithm and it is not difficult to figure out the program will return 2, which is the right answer:)


  • 0
    W
    This post is deleted!

  • 0
    W

    Yeah, your code will get the right answer, haha~ Well, the case you mention ({1, 2}, 0) in your algorithm will go into the loop, and finally return 0. If the case is ({1,2,3,4....INT_MAX},0), I think your way won't get the best time complexity. My way is to judge whether it is necessary to go into the loop ahead and thus can hold the edge case better. Am I right?


Log in to reply
 

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