问题描述:

I'm looking for an algorithm to find the first number less than X in an array of integers. Actually I'm using linear search,but I think that binary search may be better(as I already have seen sometime ago) but I don't know how to implement it myself(not implement a modified version to find the first-less than X). If there is something better than bin search,please tell me. I need of it because this array is so-much accessed and modified while the program is running.

Here's the current(trival) implementation:

int findmin(int *arr,int n,int size)

{

int i;

for(i = 0; i < size && arr[i] < n; i++)

;

return i-1;

}

This index is used the parameter input to function that insert N-value in a specific index. The index of this function and insert a number in array but still make it sorted without a sort() call at each time a new number is inserted.

It is a relevant file text parsing,parse much files and I a number considerable of characters. I need to make some effort to make the things more fast as possible(in my context and knowlege).

EDIT: The array is sorted always will be,even after insections of new numbers.

网友答案:

Binary search is no problem here. The difficult is how to check the boundary conditions and what value should be returned. Moreover, you have to take care of duplicate values. The following function will work.

    int binarySearch(int a[], int length, int value)
    {
        if (a[0] > value)
            return -1;

        int low = 0;
        int high = length-1;

        while (low<=high)
        {
            int mid = low+((high-low)/2);

            if(a[mid] >= value)
                high = mid-1;
            else
                low = mid+1;
        }

        return low-1;
    }

Test: (with duplicates)

    int arr[] = {1, 3, 4, 6, 6, 10};
    int length = sizeof(arr)/sizeof(arr[0]);

    int index = binarySearch(arr, length, 6); // will be 2
网友答案:

You have to have the array of N elements already sorted.

Set "high" to N and "low" to -1.

"Probe" element N/2 (rounding down to an int).

If the probed element is < your target, set "high" to N/2. If >, set "low" to N/2. (If ==, of course, then you have your answer.)

Repeat, probing halfway between "low" and "high".

There are boundary conditions you need to worry about, but not too complicated.

相关阅读:
Top