import java.util.Arrays; import java.util.Random; public class Main { public void Start(){ int[] array = {3, 6, 1, 4, 2, 9, 7, 8, 5, 0}; int key = 1; Arrays.sort(array);
Given a sorted array named arr of n elements, write a function to search for a given element x in arr. If the element is present, return the index of x in the array. If the element is not present, return -1. Don't forget that arrays are 0-base-indexed, meaning that the first element in the array is at index 0, and each successive element will be one higher than the one that came before.
Examples:
-
Input: arr = {10, 20, 30, 50, 60, 80, 110, 130, 140, 170}, x = 110
-
Output: 6.
-
Explanation: Element x is present at index 6.
=======================================================================================
Pseudo
How to write a binary search
-
Compare x with the middle element.
-
If x matches with the middle element, we return the mid index.
-
Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for the right half.
-
Else (x is smaller) recur for the left half.
If the above doesn't get you close enough to the answer, follow along with this in-depth pseudocode. In addition, you're welcome to use online resources to make the algorithm, but make sure you refrain from simply copying and pasting answers. If you don't understand the code that you're using, you won't learn anything.
-
Let min = 0 and max = n-1 where n is the number of elements in the array.
-
Compute guess as the average of max and min, rounded down so that it remains an integer.
-
If array[guess] equals the target, stop. You found it! Return the index of the guess.
-
If the guess was too low, meaning that array[guess] < target, then set min = guess + 1.
-
Otherwise, the guess was too high. Set max = guess - 1. Go back to step 2 and try again.
-
Continue until the value is found, or, if all of the numbers have been checked, return -1 to signal that the algorithm failed to find the number.
In addition, make sure you only edit the method binarySearch(). The parameters have been created for you.
Lastly, make sure to test your code with different values by changing the array and key values.
Test cases:
array = {} // empty array.
// result = -1.
array = {5}, key = 5; // single-element array.
// result = 0.
array = {5}, key = 0; // same as above.
// result = -1.
array = {2, 1}, key = 1; // even number of elements + unsorted.
// result = 0.
array = {5, 1, 4}, key = 4; // odd number of elements + unsorted.
// result = 1.
Step by step
Solved in 2 steps with 4 images
