-3

I was reading about arrays and I programmed the first code below . The teacher did program the second code for searching in an array for a specific number. What is the difference in ordo notation between the two following codes in java . Which code performs better and what its big O notation.

My code

public static void main(String[] args)
{

   int[] data = { 100, 110, 120, 130, 140, 150 };
   int index = binarySearch(data, 120);
   System.out.println(index);
}

private static int binarySearch(int[] data, int i)
{

   if (data.length == 0)
   {
      return -1;
   }

   for (int k = 0; k < data.length; k++)
   {
      if (data[k] == i)
      {
         return k;
      }
   }

   return -1;
}

Teacher's code

public static void main(String[] args)
{
   int[] data = { 100, 110, 120, 130, 140, 150 };
   int index = binarySearch(data, 120);
   System.out.println(index);
}

static int binarySearch(int[] keys, int v)
{
   int position;
   int begin = 0, end = keys.length - 1;
   while (begin <= end)
   {
      position = (begin + end) / 2;
      if (keys[position] == v)
      {
         return position;
      }
      else if (keys[position] < v)
      {
         begin = position + 1;
      }
      else
      {
         end = position - 1;
      }
   }
   return -1;
}
Vampire
  • 35,631
  • 4
  • 76
  • 102
senshi nakamora
  • 65
  • 1
  • 1
  • 6
  • It sounds like you are dropping your homework on us. Have even tried to find the answer yourself? Besides: your code **does not** use binary search. Don't give a method a name that does not match up to what the method is actually doing. – GhostCat May 11 '16 at 10:52
  • this is not a homework ,, the teacher code is taken from here https://users.soe.ucsc.edu/~sbrandt/13H/slides/Chapter5.pdf I said in the post that I was reading and I am learning myself .. is that clear for you now or not ? – senshi nakamora May 11 '16 at 10:55
  • In the naoming convention, Järgermeister is right - your code is not a binarysearch :) – Supahupe May 11 '16 at 11:00
  • @ Supahupe thank you ,, I see – senshi nakamora May 11 '16 at 11:01
  • @GfsdGfds Just to be precise: you just posted some code. You didn't show any evidence that you tried to solve this problem yourself. – GhostCat May 11 '16 at 12:24

2 Answers2

1

1st Solution is O(n).

2nd Solution is O(log n).

NimChimpsky
  • 46,453
  • 60
  • 198
  • 311
  • How you know that 2nd solution is O(log n) ? thank you – senshi nakamora May 11 '16 at 10:51
  • @GfsdGfds http://stackoverflow.com/a/6094889/106261 – NimChimpsky May 11 '16 at 10:54
  • @GfsdGfds because the problem (the number of array elements still to visit) is being halved in every iteration. You can do this only **log n** times, so the while loop will iterate maximum **log n** times, which is your big O time complexity. – diginoise May 11 '16 at 10:56
0

In your implementation the running time is O(n). In the below implementation, it is O(log n), during log n means it is the binary logarithm.

You can see this because the array is always divided in its middle. That is like dividing by two each time and this is the opposite of exponential opperations or also called logarithm.

Be aware that a binary search only works fine if you have a sorted arrays.

For one run, it would be slower because you first have to sort your array. In most cases, sorting is done once and searching is done multiple times - so a binary search will have a greater benefit for you.

Supahupe
  • 515
  • 2
  • 11
  • thank you .. what is the big O notation for sorting an array ? – senshi nakamora May 11 '16 at 10:54
  • That depends on the sorting algorithm that you choose. One of the faster (IMHO the fastest) sorting algorithms is merge sort which has a running time of O(n * log n) in average and O(n²) in worst case – Supahupe May 11 '16 at 10:56