Learn two different ways to complete the search of a sorted array. We'll go over the brute force method and a more elegant method.
Sorted Search
Instructions
Write a function that accepts a sorted array of integers and a number. Return the index of that number if present. The function should return -1 for target values not in the array.
Input: **Array of Integers, Integer
**Output: **An integer from -1 onwards.
**Solution 1
1 function search(numbers, target) {
2 for(let i = 0; i < numbers.length; i++) {
3 if(numbers[i] === target) {
4 return i;
5 }
6 }
7
8 return -1;
9 }
This solution is very simple. We go through the array and try to find our target.
Time
Since we're going through the whole array, the time complexity is: O(n).
Space
Since we store a set number of variables, space complexity is: 0(1).
Binary Search
We can come up with a better solution. Since the array is sorted, we can essentially jump around the array until we find the index we're looking for.
Finding a Word
Imagine looking for a word in a dictionary. Would it be efficient to go through every single word until we find the one we want? No, that would be horribly inefficient.
A better approach would be to open the dictionary halfway. If our word is alphabetically before the words in the middle page, we know our word is in the first half of the book.
We can then flip to ~1/4 of the way through the dictionary. Again, repeating the above process, we can eliminate another half of the remaining pages.
We can repeat the above steps again and again until we find our word. This ensures that even if the dictionary is huge, we can find our word much faster than if we were to go through each word individually.
Scaling
In fact, if we double the size of the dictionary by adding in more words, we would only have to repeat this process one more time. That's not much more work even though the dictionary is much thicker.
Let's turn this approach into code.
Solution 2
1 function binarySearch(numbers, target) {
2 let startindex = 0;
3 let endindex = numbers.length - 1;
4
5 if(target < numbers[startindex] || target > numbers[endindex]) {
6 return -1;
7 }
8
9 while(true) {
10 if(numbers[startindex] === target) {
11 return startindex:
12 }
13
14 if(numbers[endindex] === target) {
15 return endindex; }
17
18 if(endindex - startindex <= l) {
19 //indicates the number isn't present
20 return -1;
22
23 const middleindex = Math.floor((startindex + endindex)/2);
24
25 if(target > numbers[middlelndex]) {
26 Startindex = middlelndex + 1;
27 } else if(target < numbers[middlelndex]) {
28 endindex = middleindex - 1;
29 } else {
30 return middlelndex;
31 }
How it Works
We start by ensuring that the target is within range of the array, returning
false otherwise.
In the loop, we first check if the target is equal to the values at the beginning and end of our array. Then we check if the target is larger or smaller than the value at the center.
If it's smaller than the value at the center, we know that it's going to be somewhere in the 1st half of the array. We can focus on that.
If it's larger, we know that it can't possibly be in the first half, so we can focus on searching the 2nd half.
Over and over, we cut the amount we have to search by half until we close in on its location. If we find it along the way, we can stop and return its index.
Top comments (0)