Binary Search in Javascript

[mrchow19910319]

Imagine you have an array that contains these elements:  [1,3,4,5,2] and you want to find a specific value , let's say 4.

How can you find it? 

One way to find it is to 1st, sort the array in ascending sequence, then find the middle value, then compares the middle value to value you want to find. 

If the value you wanna find is bigger than the middle value, then you discard all the values in the array that comes before the middle value. (which means that now the start of the array is the one value that comes later than the middle value)

Then you find the new middle value and compares that to the value you want to find. Rinse and repeat, until the value you want to find === the newest middle value.

 

Here's the code snippet: 

const arr = [1,5,3,4,2];

function binary_search(arr,value){
	
	let low = 0;
	let mid = 0;
	let high = arr.length - 1;

	while(high>=low){

    mid = Math.floor((high+low)/2);

		if(value>arr[mid]){
      low = mid + 1;
	}else if(value<arr[mid]){
    high = mid - 1;
  }else{
    return arr[mid];
  }
}

return "no such value";

}

let sorted = arr.sort(function(a,b){return a-b});
console.log(binary_search(sorted,49));

 

[wasab]

Or you can do a binary search tree using the visitor pattern 

[Paul P.]

If the array is not sorted by default, sorting it then using binary search is less effective than actually iterating over each element and checking if it's the one you are looking for.

[mrchow19910319]

2 hours ago, Paul P. said:

If the array is not sorted by default, sorting it then using binary search is less effective than actually iterating over each element and checking if it's the one you are looking for.

ah... i see.

[Mira Yurizaki]

As mentioned by @Paul P., it's just faster to iterate through the array. Iterating through the array is simply an O(n) penalty. Sorting + iterating is at best O(n log(n)) plus O(log n). But that's just execution time. If memory is a constraint, then we'd have to consider other sorting algorithms which may not have O(n log(n)) complexity.

 

If my math is right for chaining algorithms, sorting + binary search in the best case is only good for about 8 items. After that, simply looking in the array is faster (I plugged "x * log(x) + log(x)" and "x" into https://www.desmos.com/calculator to get this). Optimizing for 8 items or fewer is kind of a wasted effort since 8 items is trivial in most cases.

[mrchow19910319]

1 hour ago, M.Yurizaki said:

As mentioned by @Paul P., it's just faster to iterate through the array. Iterating through the array is simply an O(n) penalty. Sorting + iterating is at best O(n log(n)) plus O(log n). But that's just execution time. If memory is a constraint, then we'd have to consider other sorting algorithms which may not have O(n log(n)) complexity.

 

If my math is right for chaining algorithms, sorting + binary search in the best case is only good for about 8 items. After that, simply looking in the array is faster (I plugged "x * log(x) + log(x)" and "x" into https://www.desmos.com/calculator to get this). Optimizing for 8 items or fewer is kind of a wasted effort since 8 items is trivial in most cases.

thank you for the info. 

may I ask, if I want to learn data structure, can I learn it in JS? 

you have any resource or tips on how should I study it?? 

I felt it is really complicated, and it seems impossible to memorize/know all the combination. 

[Mira Yurizaki]

19 minutes ago, mrchow19910319 said:

may I ask, if I want to learn data structure, can I learn it in JS? 

you have any resource or tips on how should I study it?? 

I felt it is really complicated, and it seems impossible to memorize/know all the combination. 

You can learn about data structures in JS at least on a higher level, like arrays, dictionaries, etc. But your problem is more concerned about algorithms than the data they work on.

 

As for any resources, other than buy a book about it, Wikipedia has extensive coverage on sorting algorithms that are easy to look through. Search algorithms are more scattered, but finding the right search algorithm to use really depends on what kind of data you're working on. Unless you're working on large sets of complicated data (like databases), simply iterating through them works best most of the time.

 

If anything, you have to understand your data first before you can figure out the best methods to use it.

[mrchow19910319]

2 minutes ago, M.Yurizaki said:

You can learn about data structures in JS at least on a higher level, like arrays, dictionaries, etc. But your problem is more concerned about algorithms than the data they work on.

 

As for any resources, other than buy a book about it, Wikipedia has extensive coverage on sorting algorithms that are easy to look through. Search algorithms are more scattered, but finding the right search algorithm to use really depends on what kind of data you're working on. Unless you're working on large sets of complicated data (like databases), simply iterating through them works best most of the time.

 

If anything, you have to understand your data first before you can figure out the best methods to use it.

I see. I will PM you if I have more specific questions. Thanks!