问题描述:

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.

您可能感兴趣的文章：

- jquery - AutoSubmit Form and Ajax Get Request
- c# - When I put a textbox or button in my WPF Window, it is rendering using DirectX or User32?
- c - linked-list queue, endless loop
- wso2esb - Building source code WSO2 ESB
- r - Why xts::apply.daily fails with cummin or cummax?
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**