3
\$\begingroup\$

I have to find the position (array index) of a number in an array, the number can lie in between any other two numbers in the array. I have written code for this but I want some alternative way to do this.

example: let the array be given as

float arr[]={1.5, 3.65, 4.9, 8.4, 10.6, 17.5, 19.45, 21.86, 25.67, 30.65}; 

Now I have to find the position of 12.6 in the given array, since 12.6 lies between 10.6 and 17.5 in the above array so, it should return array index as 4.

Is there any other way to do this? I know it can be done by using binary search but I don't know how to implement it (since the number is not present in array)

The array is sorted (ascending order)

#include<stdio.h>
int main()
{
int position;
int i;
float num=12.6; // position of this number has to be determined i.e. it lies between 10.6
// and 17.5 in the array given below so it should give array index as 4
float arr[]={1.5, 3.65, 4.9, 8.4, 10.6, 17.5, 19.45, 21.86, 25.67, 30.65}; // any random array

for(i=0;i<10;i++)
{
if(arr[i] > num)
{
position=i-1;
break;
}
}
printf("array index is %d",position); // this gives index as 4

return 0;
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Is this schoolwork? \$\endgroup\$ – pacmaninbw May 16 '20 at 16:30
  • \$\begingroup\$ @pacmaninbw Actually my code is taking a lot of time for doing this simple task, I just want to reduce the time to find out the array index. \$\endgroup\$ – shubham1355 May 16 '20 at 16:49
  • \$\begingroup\$ Try using pointers, a good optimizing compiler should do this for you, but if you aren't optimizing the using a pointer rather than an index should be faster. \$\endgroup\$ – pacmaninbw May 16 '20 at 17:09
3
\$\begingroup\$

Indent the Code

Most computer code is indented, in some languages indentation is used to show the level of complexity of the code, in other languages the code won't work properly unless it is indented.

Declare the Variables as They are Needed

The integer variable i can be declared in the for loop and that will limit the scope to just the for loop.

for(int i = 0; i < 10; i++)
{
    if(arr[i] > num)
    {
        position = i - 1;
        break;
    }
}

Horizontal Spacing

To make the code more readable, put spaces between the operators and the operands as shown above in the for loop example. Squashing all the code together makes it very difficult to understand what the code is actually doing.

Performance

First run the -O3 optimizer during compilation and linking. If the program were more complicated than it is then use a profiling tool such as gprof.

Linear searches are known to be a slower way to do things.

I think the position reported is off by one, if I was using this code to do an insertion sort, I wouldn't subtract one from position.

Shorten the Code.

There are 2 shorter ways to subtract 1 from position.

    --position;

and

    position -= 1;
\$\endgroup\$
1
  • 3
    \$\begingroup\$ There is no need for the combined search. You can do binary search all the way through. See how std::lower_bound does it in stl. \$\endgroup\$ – vnp May 17 '20 at 0:38
-3
\$\begingroup\$
  1. Learn basics of binary search. Understand it in and out.
  2. Now look again at your problem statement. Maybe modifying the binary search algorithm to suit your needs may just work out.(hint :see how you can use key in different ways)
  3. Try to find out all your test cases and end points. For instance what will you get if num = 0.5?
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Hope this helps this may help to find a procedure for the problem "quoted" in the question. This does not qualify as a code review here: no insight about the code presented. \$\endgroup\$ – greybeard May 17 '20 at 6:16
  • \$\begingroup\$ I will keep this in mind. Thank You. I answered because the question asked it "to do in some other way" using binary search. \$\endgroup\$ – Binary_Mode May 17 '20 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.