Mixing
Binary search algorithm check if an integer is contained in an array
I am having trouble implementing binary search within my code, can you explain how it works.
binarySearch takes an array of integers a and an integer n and uses
binary search algorithm check if n is contained in a. it returns true if n is
contained in a, as well as printing the number of decision made and false
otherwise.
import java.util.Arrays;
import java.util.Random;
public class Excersice2 {
public static void main(String args) {
int arr = createArray(10);
System.out.println("the array not sorted");
printArray(arr);
arr = sortArray(arr);
System.out.println("the array sorted");
printArray(arr);
System.out.println(binarySearch(arr,50));
}
public static void printArray(int arr)
{
System.out.println(Arrays.toString(arr));
}
public static int createArray(int n) {
int arr = new int[n];
Random rand = new Random();
for(int i = 0; i < n; i++)
arr[i] = rand.nextInt(101);
return arr;
}
public static int sortArray(int arr) {
Arrays.sort(arr);
return arr;
}
public static boolean binarySearch(int arr, int n) {
int firstIdx = 0;
int lastIdx = - 1;
int middle = (firstIdx + lastIdx)/2;
int idx = arr.length/2;
while( firstIdx <= lastIdx) {
if(binarySearch[middle] < arr);
}
}
}
The outcomes should look:
It took 2 times to find that the value 50 is contained the array. When looking through the list
java binary-search
edited Nov 20 '18 at 11:20
Michael
19.4k73470
asked Nov 20 '18 at 11:12
Hana UddinHana Uddin
11
add a comment |
I am having trouble implementing binary search within my code, can you explain how it works.
binarySearch takes an array of integers a and an integer n and uses
binary search algorithm check if n is contained in a. it returns true if n is
contained in a, as well as printing the number of decision made and false
otherwise.
import java.util.Arrays;
import java.util.Random;
public class Excersice2 {
public static void main(String args) {
int arr = createArray(10);
System.out.println("the array not sorted");
printArray(arr);
arr = sortArray(arr);
System.out.println("the array sorted");
printArray(arr);
System.out.println(binarySearch(arr,50));
}
public static void printArray(int arr)
{
System.out.println(Arrays.toString(arr));
}
public static int createArray(int n) {
int arr = new int[n];
Random rand = new Random();
for(int i = 0; i < n; i++)
arr[i] = rand.nextInt(101);
return arr;
}
public static int sortArray(int arr) {
Arrays.sort(arr);
return arr;
}
public static boolean binarySearch(int arr, int n) {
int firstIdx = 0;
int lastIdx = - 1;
int middle = (firstIdx + lastIdx)/2;
int idx = arr.length/2;
while( firstIdx <= lastIdx) {
if(binarySearch[middle] < arr);
}
}
}
The outcomes should look:
It took 2 times to find that the value 50 is contained the array. When looking through the list
java binary-search
edited Nov 20 '18 at 11:20
Michael
19.4k73470
asked Nov 20 '18 at 11:12
Hana UddinHana Uddin
11
1
Tip: Do not generate random test cases when you are first writing a solution, as you have here:rand.nextInt. You want to be able to run it in a reproducible way to prove to yourself that you're making progress and fixing bugs. By introducing randomness before you're even confident in your solution, you're making the entire thing much harder for yourself. It also means that we will never be able to reproduce the exact problems that you're experiencing.
– Michael
Nov 20 '18 at 11:22
1
Tip #2: But you can get reproducible "random" numbers if you initializeRandomwith a fixed seed; see the javadocs.
– Stephen C
Nov 20 '18 at 11:41
For an explanation of Binary Search, read en.wikipedia.org/wiki/Binary_search_algorithm. (I was going to suggest Rubber Duck debugging. Then I realized that you haven't finished coding thebinarySearchmethod. You can't debug it unless you have coded it.)
– Stephen C
Nov 20 '18 at 11:44
add a comment |
I am having trouble implementing binary search within my code, can you explain how it works.
binarySearch takes an array of integers a and an integer n and uses
binary search algorithm check if n is contained in a. it returns true if n is
contained in a, as well as printing the number of decision made and false
otherwise.
import java.util.Arrays;
import java.util.Random;
public class Excersice2 {
public static void main(String args) {
int arr = createArray(10);
System.out.println("the array not sorted");
printArray(arr);
arr = sortArray(arr);
System.out.println("the array sorted");
printArray(arr);
System.out.println(binarySearch(arr,50));
}
public static void printArray(int arr)
{
System.out.println(Arrays.toString(arr));
}
public static int createArray(int n) {
int arr = new int[n];
Random rand = new Random();
for(int i = 0; i < n; i++)
arr[i] = rand.nextInt(101);
return arr;
}
public static int sortArray(int arr) {
Arrays.sort(arr);
return arr;
}
public static boolean binarySearch(int arr, int n) {
int firstIdx = 0;
int lastIdx = - 1;
int middle = (firstIdx + lastIdx)/2;
int idx = arr.length/2;
while( firstIdx <= lastIdx) {
if(binarySearch[middle] < arr);
}
}
}
The outcomes should look:
It took 2 times to find that the value 50 is contained the array. When looking through the list
java binary-search
edited Nov 20 '18 at 11:20
Michael
19.4k73470
asked Nov 20 '18 at 11:12
Hana UddinHana Uddin
11
I am having trouble implementing binary search within my code, can you explain how it works.
binarySearch takes an array of integers a and an integer n and uses
binary search algorithm check if n is contained in a. it returns true if n is
contained in a, as well as printing the number of decision made and false
otherwise.
import java.util.Arrays;
import java.util.Random;
public class Excersice2 {
public static void main(String args) {
int arr = createArray(10);
System.out.println("the array not sorted");
printArray(arr);
arr = sortArray(arr);
System.out.println("the array sorted");
printArray(arr);
System.out.println(binarySearch(arr,50));
}
public static void printArray(int arr)
{
System.out.println(Arrays.toString(arr));
}
public static int createArray(int n) {
int arr = new int[n];
Random rand = new Random();
for(int i = 0; i < n; i++)
arr[i] = rand.nextInt(101);
return arr;
}
public static int sortArray(int arr) {
Arrays.sort(arr);
return arr;
}
public static boolean binarySearch(int arr, int n) {
int firstIdx = 0;
int lastIdx = - 1;
int middle = (firstIdx + lastIdx)/2;
int idx = arr.length/2;
while( firstIdx <= lastIdx) {
if(binarySearch[middle] < arr);
}
}
}
The outcomes should look:
It took 2 times to find that the value 50 is contained the array. When looking through the list
java binary-search
java binary-search
edited Nov 20 '18 at 11:20
Michael
19.4k73470
asked Nov 20 '18 at 11:12
Hana UddinHana Uddin
11
edited Nov 20 '18 at 11:20
Michael
19.4k73470
asked Nov 20 '18 at 11:12
Hana UddinHana Uddin
11
edited Nov 20 '18 at 11:20
Michael
19.4k73470
edited Nov 20 '18 at 11:20
Michael
19.4k73470
edited Nov 20 '18 at 11:20
Michael
19.4k73470
19.4k73470
asked Nov 20 '18 at 11:12
Hana UddinHana Uddin
11
asked Nov 20 '18 at 11:12
Hana UddinHana Uddin
11
asked Nov 20 '18 at 11:12
Hana UddinHana Uddin
11
11
1
Tip: Do not generate random test cases when you are first writing a solution, as you have here:rand.nextInt. You want to be able to run it in a reproducible way to prove to yourself that you're making progress and fixing bugs. By introducing randomness before you're even confident in your solution, you're making the entire thing much harder for yourself. It also means that we will never be able to reproduce the exact problems that you're experiencing.
– Michael
Nov 20 '18 at 11:22
1
Tip #2: But you can get reproducible "random" numbers if you initializeRandomwith a fixed seed; see the javadocs.
– Stephen C
Nov 20 '18 at 11:41
For an explanation of Binary Search, read en.wikipedia.org/wiki/Binary_search_algorithm. (I was going to suggest Rubber Duck debugging. Then I realized that you haven't finished coding thebinarySearchmethod. You can't debug it unless you have coded it.)
– Stephen C
Nov 20 '18 at 11:44
add a comment |
1
Tip: Do not generate random test cases when you are first writing a solution, as you have here:rand.nextInt. You want to be able to run it in a reproducible way to prove to yourself that you're making progress and fixing bugs. By introducing randomness before you're even confident in your solution, you're making the entire thing much harder for yourself. It also means that we will never be able to reproduce the exact problems that you're experiencing.
– Michael
Nov 20 '18 at 11:22
1
Tip #2: But you can get reproducible "random" numbers if you initializeRandomwith a fixed seed; see the javadocs.
– Stephen C
Nov 20 '18 at 11:41
For an explanation of Binary Search, read en.wikipedia.org/wiki/Binary_search_algorithm. (I was going to suggest Rubber Duck debugging. Then I realized that you haven't finished coding thebinarySearchmethod. You can't debug it unless you have coded it.)
– Stephen C
Nov 20 '18 at 11:44
1
1
Tip: Do not generate random test cases when you are first writing a solution, as you have here:
rand.nextInt. You want to be able to run it in a reproducible way to prove to yourself that you're making progress and fixing bugs. By introducing randomness before you're even confident in your solution, you're making the entire thing much harder for yourself. It also means that we will never be able to reproduce the exact problems that you're experiencing.– Michael
Nov 20 '18 at 11:22
Tip: Do not generate random test cases when you are first writing a solution, as you have here:
rand.nextInt. You want to be able to run it in a reproducible way to prove to yourself that you're making progress and fixing bugs. By introducing randomness before you're even confident in your solution, you're making the entire thing much harder for yourself. It also means that we will never be able to reproduce the exact problems that you're experiencing.– Michael
Nov 20 '18 at 11:22
1
1
Tip #2: But you can get reproducible "random" numbers if you initialize
Random with a fixed seed; see the javadocs.– Stephen C
Nov 20 '18 at 11:41
Tip #2: But you can get reproducible "random" numbers if you initialize
Random with a fixed seed; see the javadocs.– Stephen C
Nov 20 '18 at 11:41
For an explanation of Binary Search, read en.wikipedia.org/wiki/Binary_search_algorithm. (I was going to suggest Rubber Duck debugging. Then I realized that you haven't finished coding the
binarySearch method. You can't debug it unless you have coded it.)– Stephen C
Nov 20 '18 at 11:44
For an explanation of Binary Search, read en.wikipedia.org/wiki/Binary_search_algorithm. (I was going to suggest Rubber Duck debugging. Then I realized that you haven't finished coding the
binarySearch method. You can't debug it unless you have coded it.)– Stephen C
Nov 20 '18 at 11:44
add a comment |
1 Answer
1
active
oldest
votes
You can use Binary Search Algorith when you have an array of numbers and your array is sorted.
Algorithm checks if the key (the number you are looking for) is equal with the middle value of the array.
If it is, the searching is done and the key is at the middle position.
If it isnt, then the algorithm checks if the key is greater or less than the middle value.
if it is greater, then the algorithm repeats the search only at the second half of the array, taking as left the next position of the middle.
If it is less, then only at the first half taking as right the position before the middle.
And repeats that until the key is found or there is no more positions in array.
Calling the binary search method
//the number you are looking for. For example 4.
int key = 4;
//the first element of array
int left = 0;
//the last element of array
int right = arr.length - 1;
int pos = binarySearch(left, right, key);
if(pos == -1) { System.out.println("Array does not contain key"); }
else { System.out.println("Array contains key at position : " + pos); }
Binary Search Algorithm method
int binarySearch(int left, int right, int key) {
int pos;
int mid;
if(left > right) {
//there is no more positions to search
pos = -1;
} else {
//Getting the middle position of array
mid = (left + right) / 2;
//if the key is the middle positions value
if(arr[mid] == key)
pos = mid;
//if the key is less than the middle value
else if(key < arr[mid])
//repeat the search only at the first half of array
pos = binarySearch(left, mid-1, key);
else
//else if the key is greater than the middle value
//search at the second half of array
pos = binarySearch(mid+1, right, key);
}
return pos;
}
answered Nov 20 '18 at 12:12
oskozachoskozach
6615
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53391741%2fbinary-search-algorithm-check-if-an-integer-is-contained-in-an-array%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
You can use Binary Search Algorith when you have an array of numbers and your array is sorted.
Algorithm checks if the key (the number you are looking for) is equal with the middle value of the array.
If it is, the searching is done and the key is at the middle position.
If it isnt, then the algorithm checks if the key is greater or less than the middle value.
if it is greater, then the algorithm repeats the search only at the second half of the array, taking as left the next position of the middle.
If it is less, then only at the first half taking as right the position before the middle.
And repeats that until the key is found or there is no more positions in array.
Calling the binary search method
//the number you are looking for. For example 4.
int key = 4;
//the first element of array
int left = 0;
//the last element of array
int right = arr.length - 1;
int pos = binarySearch(left, right, key);
if(pos == -1) { System.out.println("Array does not contain key"); }
else { System.out.println("Array contains key at position : " + pos); }
Binary Search Algorithm method
int binarySearch(int left, int right, int key) {
int pos;
int mid;
if(left > right) {
//there is no more positions to search
pos = -1;
} else {
//Getting the middle position of array
mid = (left + right) / 2;
//if the key is the middle positions value
if(arr[mid] == key)
pos = mid;
//if the key is less than the middle value
else if(key < arr[mid])
//repeat the search only at the first half of array
pos = binarySearch(left, mid-1, key);
else
//else if the key is greater than the middle value
//search at the second half of array
pos = binarySearch(mid+1, right, key);
}
return pos;
}
answered Nov 20 '18 at 12:12
oskozachoskozach
6615
add a comment |
You can use Binary Search Algorith when you have an array of numbers and your array is sorted.
Algorithm checks if the key (the number you are looking for) is equal with the middle value of the array.
If it is, the searching is done and the key is at the middle position.
If it isnt, then the algorithm checks if the key is greater or less than the middle value.
if it is greater, then the algorithm repeats the search only at the second half of the array, taking as left the next position of the middle.
If it is less, then only at the first half taking as right the position before the middle.
And repeats that until the key is found or there is no more positions in array.
Calling the binary search method
//the number you are looking for. For example 4.
int key = 4;
//the first element of array
int left = 0;
//the last element of array
int right = arr.length - 1;
int pos = binarySearch(left, right, key);
if(pos == -1) { System.out.println("Array does not contain key"); }
else { System.out.println("Array contains key at position : " + pos); }
Binary Search Algorithm method
int binarySearch(int left, int right, int key) {
int pos;
int mid;
if(left > right) {
//there is no more positions to search
pos = -1;
} else {
//Getting the middle position of array
mid = (left + right) / 2;
//if the key is the middle positions value
if(arr[mid] == key)
pos = mid;
//if the key is less than the middle value
else if(key < arr[mid])
//repeat the search only at the first half of array
pos = binarySearch(left, mid-1, key);
else
//else if the key is greater than the middle value
//search at the second half of array
pos = binarySearch(mid+1, right, key);
}
return pos;
}
answered Nov 20 '18 at 12:12
oskozachoskozach
6615
add a comment |
You can use Binary Search Algorith when you have an array of numbers and your array is sorted.
Algorithm checks if the key (the number you are looking for) is equal with the middle value of the array.
If it is, the searching is done and the key is at the middle position.
If it isnt, then the algorithm checks if the key is greater or less than the middle value.
if it is greater, then the algorithm repeats the search only at the second half of the array, taking as left the next position of the middle.
If it is less, then only at the first half taking as right the position before the middle.
And repeats that until the key is found or there is no more positions in array.
Calling the binary search method
//the number you are looking for. For example 4.
int key = 4;
//the first element of array
int left = 0;
//the last element of array
int right = arr.length - 1;
int pos = binarySearch(left, right, key);
if(pos == -1) { System.out.println("Array does not contain key"); }
else { System.out.println("Array contains key at position : " + pos); }
Binary Search Algorithm method
int binarySearch(int left, int right, int key) {
int pos;
int mid;
if(left > right) {
//there is no more positions to search
pos = -1;
} else {
//Getting the middle position of array
mid = (left + right) / 2;
//if the key is the middle positions value
if(arr[mid] == key)
pos = mid;
//if the key is less than the middle value
else if(key < arr[mid])
//repeat the search only at the first half of array
pos = binarySearch(left, mid-1, key);
else
//else if the key is greater than the middle value
//search at the second half of array
pos = binarySearch(mid+1, right, key);
}
return pos;
}
answered Nov 20 '18 at 12:12
oskozachoskozach
6615
You can use Binary Search Algorith when you have an array of numbers and your array is sorted.
Algorithm checks if the key (the number you are looking for) is equal with the middle value of the array.
If it is, the searching is done and the key is at the middle position.
If it isnt, then the algorithm checks if the key is greater or less than the middle value.
if it is greater, then the algorithm repeats the search only at the second half of the array, taking as left the next position of the middle.
If it is less, then only at the first half taking as right the position before the middle.
And repeats that until the key is found or there is no more positions in array.
Calling the binary search method
//the number you are looking for. For example 4.
int key = 4;
//the first element of array
int left = 0;
//the last element of array
int right = arr.length - 1;
int pos = binarySearch(left, right, key);
if(pos == -1) { System.out.println("Array does not contain key"); }
else { System.out.println("Array contains key at position : " + pos); }
Binary Search Algorithm method
int binarySearch(int left, int right, int key) {
int pos;
int mid;
if(left > right) {
//there is no more positions to search
pos = -1;
} else {
//Getting the middle position of array
mid = (left + right) / 2;
//if the key is the middle positions value
if(arr[mid] == key)
pos = mid;
//if the key is less than the middle value
else if(key < arr[mid])
//repeat the search only at the first half of array
pos = binarySearch(left, mid-1, key);
else
//else if the key is greater than the middle value
//search at the second half of array
pos = binarySearch(mid+1, right, key);
}
return pos;
}
answered Nov 20 '18 at 12:12
oskozachoskozach
6615
edited Nov 20 '18 at 12:41
answered Nov 20 '18 at 12:12
oskozachoskozach
6615
answered Nov 20 '18 at 12:12
oskozachoskozach
6615
answered Nov 20 '18 at 12:12
oskozachoskozach
6615
6615
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53391741%2fbinary-search-algorithm-check-if-an-integer-is-contained-in-an-array%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Tip: Do not generate random test cases when you are first writing a solution, as you have here:
rand.nextInt. You want to be able to run it in a reproducible way to prove to yourself that you're making progress and fixing bugs. By introducing randomness before you're even confident in your solution, you're making the entire thing much harder for yourself. It also means that we will never be able to reproduce the exact problems that you're experiencing.– Michael
Nov 20 '18 at 11:22
1
Tip #2: But you can get reproducible "random" numbers if you initialize
Randomwith a fixed seed; see the javadocs.– Stephen C
Nov 20 '18 at 11:41
For an explanation of Binary Search, read en.wikipedia.org/wiki/Binary_search_algorithm. (I was going to suggest Rubber Duck debugging. Then I realized that you haven't finished coding the
binarySearchmethod. You can't debug it unless you have coded it.)– Stephen C
Nov 20 '18 at 11:44