LeetCode | 35. Search Insert Position

Description

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array. Here are few examples.
[1,3,5,6], 5 → 2    [1,3,5,6], 7 → 4
[1,3,5,6], 2 → 1   [1,3,5,6], 0 → 0

Solution

To solve this problem, we must learn about an algorithm called "BinarySearch" at first.

A java-based implementation

  • Array : must be sorted ;
  • Key compares : at most [1+lgN] ;
  • Found : If the key can be found in the array :
    • return * index* ( count from 0 ) ;        // [1,3,5,6], 5 → 2
  • Not found : If the key can not be found in the array :
    • return ( 0 - the inserted index(count from 1)) ; // [1,3,5,6], 7 → -5
public static int binarySearch(int[] a, int key) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi-lo) / 2;         //or int mid = (lo + hi)>>>1;
    if (a[mid] < key){
        low = mid + 1;
        }
     else if (a[mid] > key){
        high = mid - 1;
        }
     else
         return mid;         // key found
     }
    return -(lo + 1);        // key not found.
}

Overload

Arrays. binarySearch(object[ ], object key);
Arrays. binarySearch(object[ ], int fromIndex, int endIndex, object key);

  • Range : [*fromIndex, endIndex-1*]    
  • Found : If the key can be found in the range :
    • return index (count from 0) ;       // [1,3,5,6], 1,4,5 → 2
  • Not Found : If the key can not be found in the range :
    • object[fromIndex] < object[key] < object[endIndex-1] :
      • return (0 - the inserted index(count from 1)); // [1,3,5,6],4 → -3
    • object[key] < object[fromIndex] :
      • return (0 - (fromIndex+1));     // [1,3,5,6], 1,4,0 → -2
    • object[key] > object[endIndex-1]:
      • return (0 - (endIndex+1));     // [1,3,5,6], 1,4,9 → -5

Code

According to the description, make changes in return.

return lo;
Comments
Write a Comment