O (log n) to find the best insertion position in a sorted array

Question

I am trying to create an algorithm that will find the best position to insert a target into an already sorted array.

The goal is to either return the position of the element, if it exists in the list, or return the position at which it will go in order to sort the list.

So I have a list:

0 1 2 3 4 5 6 --------------------------------- | 1 | 2 | 4 | 9 | 10 | 39 | 100 | --------------------------------- 

And my target element is 14 It should return an index position of 5

The pseudocode I currently have is:

 array = generateSomeArrayOfOrderedNumbers() number findBestIndex(target, start, end) mid = abs(end - start) / 2 if (mid < 2) // Not really sure what to put here return start + 1 // ?? if (target < array[mid]) // The target belongs on the left side of our list // return findBestIndex(target, start, mid - 1) else // The target belongs on the right side of our list // return findBestIndex(target, mid + 1, end) 

I'm not quite sure what to say. I tried using the binary search approach, but this is the best I could come up with after 5 rewrites or so.

Answer 1

There are several problems in your code:

 mid = abs(end - start) / 2 

This is not the middle between start and end , it is half the distance between them (rounded to the nearest whole). Later you use it as if it is really a valid index:

 findBestIndex(target, start, mid - 1) 

It is not so. You probably wanted to use mid = (start + end) // 2 or something here. You will also skip a few indexes because you skip the middle:

 return findBestIndex(target, start, mid - 1) ... return findBestIndex(target, mid + 1, end) 

Now your base case should be expressed a little differently. A good candidate is the condition

 if start == end 

Because now you know for sure that you’ve finished the search. Note that you should also consider the case where all elements of the array are less than target , so you need to insert it at the end.

I do not often look for a binary file, but if so, how

Binary search is something that is surprisingly hard to understand if you have never done it before. I usually use the following pattern if I do a binary search:

 lo, hi = 0, n // [lo, hi] is the search range, but hi will never be inspected. while lo < hi: mid = (lo + hi) // 2 if check(mid): hi = mid else: lo = mid + 1 

Provided that check is a monotone binary predicate (it is always false to some point and true from this point), after this loop lo == hi will be the first number in the range [0..n] with check(lo) == true . check(n) implies that it is true (this is part of the magic of this approach).

So, what is a monotone predicate that is true for all indices, including after our target position, and false for all positions before?

If we think about it, we want to find the first number in the array that is larger than our goal, so we just plug it in and we are good to go:

 lo, hi = 0, n while lo < hi: mid = (lo + hi) // 2 if (a[mid] > target): hi = mid else: lo = mid + 1 return lo; 

Answer 2

You are on the right track.

First, you don't need abs in mid = abs(end + start) / 2

Suppose abs here means an absolute value, because the end should always be no less than start if there is no error in your code. Thus, abs never helps, but it can potentially hide your problem, making it difficult to debug.

You don't need an if (mid < 2) section if (mid < 2) , nothing special in the middle of less than two.

 array = generateSomeArrayOfOrderedNumbers() int start = 0; int end = array.size(); int findBestIndex(target, start, end){ if (start == end){ //you already searched entire array, return the position to insert if (stat == 0) return 0; // if it the beginning of the array just return 0. if(array[start] > target) return start -1; //if last searched index is bigger than target return the position before it. else return start; } mid = (end - start) / 2 // find correct position if(target == array[mid]) return mid; if (target < array[mid]) { // The target belongs on the left side of our list // return findBestIndex(target, start, mid - 1) } else { // The target belongs on the right side of our list // return findBestIndex(target, mid + 1, end) } } 

Answer 3

I solved this by counting the number of elements that are strictly less (<) than the key to insert. The recovered counter is the insertion position. Here is a ready-to-use implementation in Java:

 int binarySearchCount(int array[], int left, int right, int key) { if(left > right) { return -1; // or throw exception } int mid = -1; //init with arbitrary value while (left <= right) { // Middle element mid = (left + right) / 2; // If the search key on the left half if (key < array[mid]) { right = mid - 1; } // If the search key on the right half else if (key > array[mid]) { left = mid + 1; } // We found the key else { // handle duplicates while(mid > 0 && array[mid-1] == array[mid]) { --mid; } break; } } // return the number of elements that are strictly smaller (<) than the key return key <= array[mid] ? mid : mid + 1; } 

Answer 4

this is the code i used:

 int binarySearch( float arr[] , float x , int low , int high ) { int mid; while( low < high ) { mid = ( high + low ) / 2; if( arr[mid]== x ) { break; } else if( arr[mid] > x ) { high=mid-1; } else { low= mid+1; } } mid = ( high + low ) / 2; if (x<=arr[mid]) return mid; else return mid+1; } 

the point is that even when low becomes equal to the maximum, you should check.

see example: 0.5-> 0.75 and you are looking for a true position of 0.7 or 1.

in both cases, when exiting the while: low = high = 1 cycle, but one of them should be placed in position 1, and the other in position 2.