原创转载请注明出处:http://agilestyle.iteye.com/blog/2273610
Binary Search原理
package org.fool.test; public class BinarySearch { public static int binarySearch(int[] nums, int num) { int low = 0; int high = nums.length - 1; while (low <= high) { int mid = (low + high) / 2; if (num > nums[mid]) { low = mid + 1; } else if (num < nums[mid]) { high = mid - 1; } else { return mid; } } return -1; } public static void main(String[] args) { int[] nums = { 12, 23, 34, 45, 56, 67, 77, 89, 90 }; System.out.println(binarySearch(nums, 12)); System.out.println(binarySearch(nums, 45)); System.out.println(binarySearch(nums, 67)); System.out.println(binarySearch(nums, 89)); System.out.println(binarySearch(nums, 99)); } }
get square root of a number
核心思想:二分查找
1.define an initial range of (start, end)
2.keep testing mid^2 to approach value
3.update start or end to mid
4.stop when certain precision is achieved or exact square root is computed
package org.fool.java.test; public class SqrtTest { public static void main(String[] args) { System.out.println("sqrt of 50 is " + sqrt(50)); System.out.println("sqrt of 81 is " + sqrt(81)); System.out.println("sqrt of 99 is " + sqrt(99)); } private static double sqrt(double a) { if (a < 0) { return -1; } if (a == 0 || a == 1) { return a; } double precision = 0.00000001; double start = 0; double end = a; // define these 2 start/end values because usually 0 < sqrt(a) < a // however, if a < 1, then 0 < a < sqrt(a) if (a < 1) { end = 1; } // define a loop to continue if the precision is not yet achieved while (end - start > precision) { double mid = (start + end) / 2; double midSqr = mid * mid; if (midSqr == a) { return mid; // the exact sqrt value } else if (midSqr < a) { start = mid; // shift focus to bigger half } else { end = mid; // shift focus to smaller half } } // if not find the exact sqrt value, return the approximated value with the defined precision return (start + end) / 2; } }
Console Output
Count Occurance of a given number in sorted array
solution 1: linear search in O(N)
solution 2: binary search(preferred)
need to add boundary checking for each sub-array
package org.fool.java.test; public class NumberOccurrenceTest { public static void main(String[] args) { int[] nums = {1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 8, 9}; System.out.println("Occurrence of num 2 is " + getOccurrence(2, nums, 0, nums.length - 1)); System.out.println("Occurrence of num 6 is " + getOccurrence(6, nums, 0, nums.length - 1)); System.out.println("Occurrence of num 7 is " + getOccurrence(7, nums, 0, nums.length - 1)); System.out.println("Occurrence of num 17 is " + getOccurrence(17, nums, 0, nums.length - 1)); } private static int getOccurrence(int k, int[] numbers, int startIndex, int endIndex) { if (endIndex < startIndex) { return 0; } if (numbers[startIndex] > k) { // smallest element is larger than k return 0; } if (numbers[endIndex] < k) { // largest element is smaller than k return 0; } if (numbers[startIndex] == k && numbers[endIndex] == k) { // if all elements are k return endIndex - startIndex + 1; } int midIndex = (startIndex + endIndex) / 2; // a sub-array may possibly contain some other k if (numbers[midIndex] == k) { return 1 + getOccurrence(k, numbers, startIndex, midIndex - 1) + getOccurrence(k, numbers, midIndex + 1, endIndex); } else if (numbers[midIndex] > k) { // only smaller half may contain k return getOccurrence(k, numbers, startIndex, midIndex - 1); } else { // only bigger half may contain k return getOccurrence(k, numbers, midIndex + 1, endIndex); } } }
Console Output
Find the 1st index of given number in a sorted array allowing duplicates
核心思想:二分查找
package org.fool.java.test; public class FindFirstIndexTest { public static void main(String[] args) { int[] nums = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8, 8, 9}; System.out.println("First index of number 1 is " + getFirstIndex(nums, 1, 0, nums.length - 1)); System.out.println("First index of number 2 is " + getFirstIndex(nums, 2, 0, nums.length - 1)); System.out.println("First index of number 3 is " + getFirstIndex(nums, 3, 0, nums.length - 1)); System.out.println("First index of number 4 is " + getFirstIndex(nums, 4, 0, nums.length - 1)); System.out.println("First index of number 5 is " + getFirstIndex(nums, 5, 0, nums.length - 1)); System.out.println("First index of number 8 is " + getFirstIndex(nums, 8, 0, nums.length - 1)); } // define a same header as a normal binary search // nums are the sorted array // a is the number we are looking for // start and end are the two index values to keep track of the current focus sub-array private static int getFirstIndex(int[] nums, int a, int start, int end) { if (end < start) { return -1; } if (nums[start] > a) { return -1; } if (nums[end] < a) { return -1; } // need to check if first element is a if (nums[start] == a) { return start; } int mid = (start + end) / 2; if (nums[mid] == a) { // we have 2 choices, either mid position is candidate, or the index we find in the left half int leftIndex = getFirstIndex(nums, a, start, mid - 1); // recursive call return leftIndex == -1 ? mid : leftIndex; } else if (nums[mid] > a) { // which means a can only appear in the left half return getFirstIndex(nums, a, start, mid - 1); } else { // which means only possible in the right half return getFirstIndex(nums, a, mid + 1, end); } } }
Console Output
Reference
https://www.youtube.com/watch?v=XvsQ68jUc2U&index=50&list=PLlhDxqlV_-vkak9feCSrnjlrnzzzcopSG
https://www.youtube.com/watch?v=W8923B642PQ&list=PLlhDxqlV_-vkak9feCSrnjlrnzzzcopSG&index=49
https://www.youtube.com/watch?v=bvzJw9CVmkI&index=45&list=PLlhDxqlV_-vkak9feCSrnjlrnzzzcopSG
相关推荐
A binary search algorithm (or binary chop) is a technique for finding a particular value in a sorted list. It makes progressively better guesses, and closes in on the sought value, by comparing an ...
matlab开发-BinarySearch。对数据向量中的值进行二进制搜索。
matlab开发-Binarysearch。bsearch对已排序的数组执行二进制搜索
1975年,来自斯坦福大学的Jon Louis Bentley在ACM杂志上发表的一篇论文:Multidimensional Binary Search Trees Used for Associative Searching 中正式提出和阐述的了把空间划分为多个部分的k-d树。
Binary Search Tree 利用C++實現 Binary Search Tree
最小成本二分检索树optimal binary optimal binary
BinarySearch
实现折半查找的程序 希望大家功能学习,共同进步
关于最优二叉查找树的开山之作,介绍了最优二叉查找树的概念,以及构造最优二叉查找树的动态规划算法,来自D. E. KNUTH,发表于1971年,亦可从这里下载:...
http://blog.csdn.net/xkzju2010/article/details/46399155
The most commonly used binary search variant was first published by Hermann Bottenbruch in 1962 and hasn't notably changed since. Below I'll describe several novel variants with improved performance. ...
C#,二叉搜索树(Binary Search Tree)的迭代方法与源代码 二叉搜索树(BST,Binary Search Tree)又称二叉查找树或二叉排序树。 一棵二叉搜索树是以二叉树来组织的,可以使用一个链表数据结构来表示,其中每一个...
binary search tree program using c language
这是一个用c++做的简单的折半查找算法,在递增的序列数组中,找到对应的数字的位置
binarysearch.py
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with keys less than the node's key. The right ...
Binary Search Tree.cpp
Build an optimal binary search tree using dynamic programming.