Binary search algorithm in c

Question

I'm trying to create a function int find_pos(int item, int a[], int len) that works as follows:

Returns the index in array of the key t that is the the successor of k, if one exists, else return KEY_NOT_FOUND.

Key t is the successor of k, if t is the smallest key stored in sda->buffer such that t >= k.

const int KEY_NOT_FOUND = -1;

int find_pos(int item, int a[], int len) {
 int low = 0;
 int high = len-1;
 if (a[0] >= item && len == 1) {
 return 0;
 }
 if(a[0] < item && len == 1) {
 return KEY_NOT_FOUND;
 }
 while (low <= high) {
 int mid = low + (high - low) / 2;
 if (a[mid] == item) {
  return mid;
 } else if (a[mid] < item) {
   low = mid + 1;
 } else {
   high = mid - 1;
 }
 if(a[high] < item) {// invalid size read of 4
  return high + 1;
 }
 }
 return KEY_NOT_FOUND;
}

However, it may cause invalid read size read of 4 at

if(a[high] < item)

Can somone explain(or give an example) why does this line cause invalid read size read of 4? Thanks in advance.

Congratulations on using valgrind to spot such problems.

Jonathan Leffler
– Jonathan Leffler

2013-07-23 17:43:44 +00:00
Commented Jul 23, 2013 at 17:43 — Jonathan Leffler
– Jonathan Leffler, Commented Jul 23, 2013 at 17:43

Doug Currie · Accepted Answer · 2013-07-23 17:29:52Z

3

Let's say low == high == 0 the start of the while loop.

So, mid == 0

Then the code does high = mid - 1; So, high is now negative, and a[high] is an illegal access.

answered Jul 23, 2013 at 17:29

Doug Currie

41.4k1 gold badge104 silver badges121 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Binary search algorithm in c

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related