Kevin Powell - Community•2y ago

does it work for unsotred array?

function findMe (target, start, end){
      
      if(start > end) 
        return "Not Found" ;
      
      const middle = Math.floor( (start + end) / 2);
      
      if( arr[middle] === target ) 
        return `found at index ${middle}`;
        
      if( arr[middle] > target )
        return findMe( target, start, middle-1 );
        
      if( arr[middle] < target )
        return findMe( target, middle+1, end);
        
    }

function findMe (target, start, end){
      
      if(start > end) 
        return "Not Found" ;
      
      const middle = Math.floor( (start + end) / 2);
      
      if( arr[middle] === target ) 
        return `found at index ${middle}`;
        
      if( arr[middle] > target )
        return findMe( target, start, middle-1 );
        
      if( arr[middle] < target )
        return findMe( target, middle+1, end);
        
    }

since it's checking if arr[middle] is less than or bigger than the target if u given unsorted array for example

const arr = [3,1,2]

const arr = [3,1,2]

and we r looking for 3 then it'll first land on 1, then check if 1 is smaller or bigger than 3. Since it's smaller than 3 it'll look on the right side but 3 in on the left side. so does that mean it'll only work with sorted array or am I getting something wrong?? i do know how to sort an array btw xD

26 Replies

glutonium•2y ago

also, a side question, if u have some array containing some objects

arr = [ {..}, {..}, {..} ]

arr = [ {..}, {..}, {..} ]

how does sortation work for that? based of the first char of the first key?

13eck•2y ago

That sorting algo requires the array to be pre-sorted, yes. So you'd need to do that first, but that also creates a lot more things you need to do, like copying the array, sorting the copy, finding the index in the copied array, then finding that entry in the original array and returning that index To make a copy of the array you'd need to

const arr1 = [3,1,2];
const findMe = (target, start, end, arr) => {
  const copy = arr.slice().sort();
  // finish here using copy
}

const arr1 = [3,1,2];
const findMe = (target, start, end, arr) => {
  const copy = arr.slice().sort();
  // finish here using copy
}

glutonium•2y ago

is it that nescessary to find the actual index from the original one? we can just use the sorted one for everything no?

13eck•2y ago

Note that array.sort() sorts the array based on strings, not numbers (as everything can be coerced to strings) so 2 is greater than 20.

glutonium•2y ago

hmm.. wouldn't arr.sort() work fine??

13eck•2y ago

That depends on what you're doing with the array .sort() mutates the array, so doing arr.sort() will change the initial array. Depending on what the array is being used for that's probably a bad thing

glutonium•2y ago

is dat case u can also use the

arr.sort( (a,b) => return a - b )

arr.sort( (a,b) => return a - b )

right?? oke got it

13eck•2y ago

Yes, but you don't need return in a one-line arrow function. If there are no {} the result is implicitly returned

glutonium•2y ago

aaah so u can't directly do

let copy = arr.sort();

let copy = arr.sort();

?? it'll still mess with the original one??

13eck•2y ago

arr.sort( (a,b) => return a - b ) === arr.sort( (a,b) => a - b )

arr.sort( (a,b) => return a - b ) === arr.sort( (a,b) => a - b )

glutonium•2y ago

aaah okeey got it

13eck•2y ago

Yes. Calling .sort() modifies the array it's called on. .slice() creates a copy of the array being sliced

glutonium•2y ago

what about the Array from

13eck•2y ago

Array.from() creates an array from another iterable, so it's not doing anything to the original array

glutonium•2y ago

hmm..so slice returns a new array?? ok got it

13eck•2y ago

Yes, it "slices" the initial array from start to end (Array.slice(start, end)). With no params passed it slices the entire array https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/slice

glutonium•2y ago

and another question, when u r dealing with BIG array dataset, wouldn't sorting take a lot of timd?? aaah got it.. tnx ❤️

13eck•2y ago

As for this question, it sorts the objects as if they're strings. If you want it to be based on a specific value in the object you need to use that in your comparator function

glutonium•2y ago

got it.. and what about this?

13eck•2y ago

The bigger the dataset the longer it takes to sort, yes. And depending on the sorting algo used it can take more or less time.

glutonium•2y ago

hmm i see.. if we need sorting to use binary search and sorting takes additional time then is that still faster than normal for loop search??

13eck•2y ago

It depends 😜 If the item you're looking for is at the beginning of the array than it's easier to for-loop it But if the item is at the end then sorting then searching is faster 😉 How you do things is very much dependent on what you're trying to accomplish. With your questions I'm not sure if you're learning sorting algos or if you think binary search is the answer to the question you haven't asked yet Because if you have a bunch of objects then you'd most likely be better off storing them in a hashmap (new Map()) than an array as finding an item is as easy as map.get(key) instead of array.find( (el) => el.key === key)

glutonium•2y ago

there isn't any particular thing I'm trying to accomplish ahaha it's just questions that pop up mind that I'm asking like when i got to know of binary search I checked what it is, then when playing around with the code I come in realization that it doesn't work for unsotred array so I asked that.. then as I was thinking about sorting it came to my mind, if numbers r sorted like this and strings like this how does it sort objects so i asked that as well ahaha but then i asked myself, if the whole point of binary search is to find item in less time wouldn't sorting take time to sort? it's just random things that pop up in mind.. xD but yaa, tnx for the help.. much appreciation ❤️

13eck•2y ago

If you're into sorting algos, check out mergesort: https://en.wikipedia.org/wiki/Merge_sort

Merge sort

In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neu...

13eck•2y ago

There are a lot of others, but mergesort is one of the best https://en.wikipedia.org/wiki/Sorting_algorithm

glutonium•2y ago

okii..tnx❤️

Gaming

Programming

does it work for unsotred array?