4 Replies - 276 Views - Last Post: 15 May 2014 - 04:18 PM Rate Topic: -----

#1 smalld01  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 23
  • Joined: 25-February 14

Binary Search method

Posted 14 May 2014 - 06:47 PM

We are required to write a binary‐search method to find an int within an array of ints. Without using any functions besides the basics (for loops, if statements, etc.)

I have this so far:

public int binarySearch(int[] ints, int n) {
    for(int i = 0; i < ints.length; i++) {
        if(ints[i] == n) {
            return ints[i];
        }
    }
}



Does this look somewhat correct?

Is This A Good Question/Topic? 0
  • +

Replies To: Binary Search method

#2 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7737
  • View blog
  • Posts: 13,070
  • Joined: 19-March 11

Re: Binary Search method

Posted 14 May 2014 - 09:08 PM

No, that's a linear search. A binary search reduces the search space by fifty percent on each iteration, so the time it takes is proportional to log(n) in the worst case. A linear search reduces the search space by one on each iteration, and so it takes time proportional to n.

I'm starting to think you should spend more time with your books and less time posting every half-assed stab at an answer that you come up with.
I think that would help you a lot more.
Was This Post Helpful? 0
  • +
  • -

#3 smalld01  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 23
  • Joined: 25-February 14

Re: Binary Search method

Posted 15 May 2014 - 03:02 PM

So how would I rearrange my if statement to get started on sorting it the way you explained?
Was This Post Helpful? 0
  • +
  • -

#4 astonecipher  Icon User is offline

  • Major DIC Head
  • member icon

Reputation: 670
  • View blog
  • Posts: 2,946
  • Joined: 03-December 12

Re: Binary Search method

Posted 15 May 2014 - 03:22 PM

A binary search splits the array in half. The first decision it makes is, does it need to search the lower haf of the array or the upper half.

In order to do that it either is passed a sorted array or sorts it within the method.
Was This Post Helpful? 0
  • +
  • -

#5 smalld01  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 23
  • Joined: 25-February 14

Re: Binary Search method

Posted 15 May 2014 - 04:18 PM

This is what I came up with (after going through selectionSort in ascending order):

public int binarySearch(int[] ints, int n) {
    selectionSort(ints);
    int low = 0;
    int high = ints.length - 1;
    int mid = (low + high) / 2;
    while(low <= high && (ints[mid] != n)){
        if(ints[mid] < n) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
        mid = (low + high) /2;
    }
    if(low > high) {
        mid = -1; //returns -1 if n is not in the array of ints
    }
    return mid;
}


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1