Arrays Study Guide - Revision history

Admin: Fix math: remove stray space before \log in O(\log N) (via update-page on MediaWiki MCP Server)

2026-06-14T23:17:49Z

Fix math: remove stray space before \log in O(\log N) (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 23:17, 14 June 2026
Line 77:		Line 77:
	===Binary Search===		===Binary Search===

	Binary search is a much faster and more sophisticated way to searching things in <math>O( \log N)</math> time. This requires a sorted array, and takes advantage of the sorted order to rule out half of the array it is considering at each step.		Binary search is a much faster and more sophisticated way to searching things in <math>O(\log N)</math> time. This requires a sorted array, and takes advantage of the sorted order to rule out half of the array it is considering at each step.
	* Public/private method: public method takes no indices, private method takes 2 indices		* Public/private method: public method takes no indices, private method takes 2 indices
	* Start with your array, your target, and your lo and hi index; at each step, compute a mid index		* Start with your array, your target, and your lo and hi index; at each step, compute a mid index

2017-08-22T02:57:25Z

Insertion Sort

← Older revision		Revision as of 02:57, 22 August 2017
Line 48:		Line 48:
	===Insertion Sort===		===Insertion Sort===

	Insertion sort is a simple algorithm that involves two nested ~~lists~~, and is therefore quadratic complexity.		Insertion sort is a simple algorithm that involves two nested loops, and is therefore quadratic complexity.
	* Stepping through the list one element at a time, such that everything before your pointer is sorted.		* Stepping through the list one element at a time, such that everything before your pointer is sorted.
	* Start with a reference to the last sorted element		* Start with a reference to the last sorted element

2017-07-06T01:39:47Z

Sequential Search

← Older revision		Revision as of 01:39, 6 July 2017
Line 65:		Line 65:
	===Sequential Search===		===Sequential Search===

	Sequential search is the simplest (not fastest) way to look for something. Simplest possible imaginable algorithm.		Sequential search is the simplest (not fastest) way to look for something. Simplest possible imaginable algorithm. Runs in <math>O(N)</math> time.

	<pre>		<pre>

2017-07-06T01:39:31Z

Binary Search

← Older revision		Revision as of 01:39, 6 July 2017
Line 77:		Line 77:
	===Binary Search===		===Binary Search===

	Binary search is a much faster and more sophisticated way to searching things in <math>O(log N)</math> time. This requires a sorted array, and takes advantage of the sorted order to rule out half of the array it is considering at each step.		Binary search is a much faster and more sophisticated way to searching things in <math>O( \log N)</math> time. This requires a sorted array, and takes advantage of the sorted order to rule out half of the array it is considering at each step.
	* Public/private method: public method takes no indices, private method takes 2 indices		* Public/private method: public method takes no indices, private method takes 2 indices
	* Start with your array, your target, and your lo and hi index; at each step, compute a mid index		* Start with your array, your target, and your lo and hi index; at each step, compute a mid index

2017-07-06T01:39:00Z

Binary Search

← Older revision		Revision as of 01:39, 6 July 2017
Line 89:		Line 89:

	def private_binary_search(array, target, lo, hi):		def private_binary_search(array, target, lo, hi):

	if(lo>hi)		if(lo>hi)
	return not found		return not found

	mid = (lo+hi)/2		mid = (lo+hi)/2
	if( A[mid] > target )		if( A[mid] > target )

2017-07-06T01:38:49Z

Binary Search

← Older revision		Revision as of 01:38, 6 July 2017
Line 76:		Line 76:

	===Binary Search===		===Binary Search===

			Binary search is a much faster and more sophisticated way to searching things in <math>O(log N)</math> time. This requires a sorted array, and takes advantage of the sorted order to rule out half of the array it is considering at each step.
			* Public/private method: public method takes no indices, private method takes 2 indices
			* Start with your array, your target, and your lo and hi index; at each step, compute a mid index
			* Base case: lo index passed hi index, return negative
			* Recursive case: check which case: less than mid (call yourself with lo to mid-1), greater than mid (call yourself with mid+1 to hi), and equals (done)

			<pre>
			def public_binary_search(array, target):
			private_binary_search(array, target, 0, length(array)-1)


			def private_binary_search(array, target, lo, hi):

			if(lo>hi)
			return not found

			mid = (lo+hi)/2
			if( A[mid] > target )
			return private_binary_search(array, target, lo, mid-1)
			else if( A[mid] < target )
			return private_binary_search(array, target, mid+1, hi)
			else
			return mid
			</pre>

	==Flags==		==Flags==

2017-07-06T01:32:21Z

Insertion Sort

@@ Line 62: / Line 62: @@
          decrement j
 </pre>
 ==Flags==

2017-07-06T01:30:17Z

Insertion Sort

2017-07-06T01:30:05Z

Fisher Yates Shuffle

@@ Line 45: / Line 45: @@
      decrement i
 </pre>
 ==Flags==

2017-07-06T01:24:06Z

Java

← Older revision		Revision as of 01:24, 6 July 2017
Line 25:		Line 25:
	* binarySearch(A,x) - perform binary search for x in A		* binarySearch(A,x) - perform binary search for x in A

			==Principal Operations and Algorithms==

			Important algorithms include:
			* fisher-yates shuffle
			* insertion sort
			* sequential search
			* binary search

			===Fisher Yates Shuffle===

			Fisher Yates shuffle is a technique for shuffling arrays.
			* Pointer that starts and end and moves to front
			* Randomly swap the pointer with an item between it and the front

			<pre>
			for i in range (n-1) to (0):
			j = random number between 0 and i
			swap array[i], array[j]
			decrement i
			</pre>

	==Flags==		==Flags==