Binary search using c programming

Question

Given an array of integers which is sorted in ascending order, and an integer target, write a function to search target in the array. If the target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

I solved the above question using the following code:

int search(int* nums, int numsSize, int target){

    int l = 0;
    int r = numsSize -1;
    int result = -1;
    
    while(l <= r)
    {
        int mid = (l + (r-l))/2;
        
        if(nums[mid] == target)
            return result = nums[mid];
        if(nums[mid] < target)
            return l = mid + 1;
        else
            return r = mid - 1;
    }
    return result;
}

But I am still not getting the right answer. Please help.

Under what conditions are you getting the wrong answer? What is an array you are searching? for what target value? What result are you expecting, and what result are you getting? — abelenky
– abelenky, Commented Oct 11, 2021 at 13:55
If you have only 1 element in the array (l == r) you automatically return -1 even if that element matches the target. — Gerhardh
– Gerhardh, Commented Oct 11, 2021 at 14:25
@500-InternalServerError The value returned should be mid as pointed out in Corina's answer below. — nielsen
– nielsen, Commented Oct 11, 2021 at 16:33

kiran Biradar · Accepted Answer · 2021-10-11 13:57:30Z

3

You are returning the newly calculated l and r value.

if(nums[mid] < target)
    return l = mid + 1;
else
    return r = mid - 1;

You just need to update them and keep searching the element.

if(nums[mid] < target)
    l = mid + 1;
else
    r = mid - 1;

answered Oct 11, 2021 at 13:57

kiran Biradar

12.8k3 gold badges21 silver badges44 bronze badges

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

1 Comment

Sreelakshmi Over a year ago

After making these changes, I am getting TIME LIMIT EXCEEDED as result

Corina M · Accepted Answer · 2021-10-11 14:26:20Z

3

Corrected code:

int search(int* nums, int numsSize, int target){

    int l = 0;
    int r = numsSize -1;
    int result = -1;
    printf("%d %d %d\n", numsSize, target, nums[0]);

    while(l <= r)
    {
        int mid = l + (r - l) / 2;
        
        if(nums[mid] == target)
            return result = mid;
        if(nums[mid] < target)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return result;
}

The errors:

You computed wrongly the mid, it's not:

int mid = (l + (r-l))/2;

Correct version is:

int mid = l + (r - l) / 2;

You should not use return here because you break the loop.

if(nums[mid] < target)
        return l = mid + 1;
    else
        return r = mid - 1;

    if(nums[mid] == target)
          return result = nums[mid];

Here you should return the mid, the position of the target value, not the value itself.

edited Oct 11, 2021 at 14:26

answered Oct 11, 2021 at 14:11

Corina M

1521 silver badge7 bronze badges

1 Comment

Jonathan Leffler Over a year ago

You don't need the assignment in return result = mid; (simply return mid;), and then you can eliminate result altogether and end with return -1;.

Pushkar Jk · Accepted Answer · 2022-03-11 23:12:09Z

-1

Try this: It is Java though

 public int search(int[] nums, int target) {
    int l = 0;
    int r = nums.length - 1;
    while(l<=r){
        
        int mid = (l+r)/2;
        if(target == nums[l]){
            return l;
        } else if (target == nums[r]){
            return r;
        } else if(target == nums[mid]){
            return mid;
        }
        else if(target > nums[mid]){
            l = mid;
            r = r - 1;
        }
        else {
            l = l + 1;
            r = mid;
        }
    }
    return -1;
}

answered Mar 11, 2022 at 23:12

Pushkar Jk

1

1 Comment

beeselmane Over a year ago

This is a C question, providing java code with no explanation doesn't really answer the question.

Leonardo Alves Machado · Accepted Answer · 2022-03-14 14:53:20Z

-1

solved using python

def search(self, nums, target):
    
    lowerIndex = 0
    higherIndex = len(nums) -1

    while lowerIndex < higherIndex:
        middle = (lowerIndex + higherIndex) // 2
        mid_number = nums[middle]
    
        if mid_number == target:
            return middle
    
        elif mid_number > target:
            lowerIndex = middle + 1
        elif mid_number < target:
            higherIndex = middle -1
    return -1

edited Mar 14, 2022 at 14:53

Leonardo Alves Machado

2,84711 gold badges44 silver badges57 bronze badges

answered Mar 13, 2022 at 1:56

DanielMaina

11 bronze badge

1 Comment

Abhishek Dutt Over a year ago

It is written in the question that the author wants the code in C only.

Collectives™ on Stack Overflow

Binary search using c programming

4 Answers 4

1 Comment

1 Comment

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

1 Comment

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related