C Program to Perform Uniform Binary Search

This C program performs uniform binary search.

Uniform binary search is an optimization of the classic binary search algorithm invented by Donald Knuth and given in Knuth’s The Art of Computer Programming. It uses a lookup table to update a single array index, rather than taking the midpoint of an upper and a lower bound on each iteration; therefore, it is optimized for architectures (such as Knuth’s MIX) on which

a table lookup is generally faster than an addition and a shift, and
many searches will be performed on the same array, or on several arrays of the same length

Here is the source code of the C program to uniform binary search on integer array. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#define LOG_N 42
```
```
 
```
```
static int delta[LOG_N];
```
```
 
```
```
void make_delta(int N)
```
```
{
```
```
    int power = 1;
```
```
    int i = 0;
```
```
    do {
```
```
        int half = power;
```
```
        power <<= 1;
```
```
        delta[i] = (N + half) / power;
```
```
    } while (delta[i++] != 0);
```
```
}
```
```
 
```
```
int unisearch(int *a, int key)
```
```
{
```

    int i = delta[0]-1;  /* midpoint of array */

```
    int d = 0;
```
```
 
```
```
    while (1) {
```
```
        if (key == a[i]) {
```
```
            return i;
```
```
        } else if (delta[d] == 0) {
```
```
            return -1;
```
```
        } else {
```
```
            if (key < a[i]) {
```
```
                i -= delta[++d];
```
```
            } else {
```
```
                i += delta[++d];
```
```
            }
```
```
        }
```
```
    }
```
```
}
```
```
 
```
```
#define N 10
```
```
int main(void)
```
```
{
```

    int num, a[N] = {1,3,5,6,7,9,14,15,17,19};

```
    make_delta(N);
```

    printf("\nEnter an element to search: ");

```
    scanf("%d", &num);
```

    printf("%d is at index %d\n", num, unisearch(a, num));

```
    return 0;
```
```
}
```

$ gcc uniformbinarysearch.c -o uniformbinarysearch
$ ./uniformbinarysearch
 
Enter an element to search: 19
19 is at index 9

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

« Prev - C Program to Implement Shaker Sort

» Next - C Program to Find kth Largest Element in a Sequence

Next Steps:

Get Free Certificate of Merit in C Programming
Participate in C Programming Certification Contest
Become a Top Ranker in C Programming
Take C Programming Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Practice Computer Science MCQs
Buy C Books
Apply for Computer Science Internship
Apply for C Internship
Practice BCA MCQs

Recommended Articles: