原创转载请注明出处: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 ...
标题中的"BinarySearch"指的是二分查找算法,这是一种在有序数组中查找特定元素的搜索算法。它的基本思想是将数组分为三个部分:小于目标值的元素、等于目标值的元素和大于目标值的元素,然后逐步缩小搜索范围,直到...
在Java编程语言中,`Arrays`类是Java.util包下的一个非常重要的工具类,它提供了大量用于操作数组的静态方法,其中包括我们今天要讨论的`binarySearch()`方法。`Arrays.binarySearch()`方法允许我们在有序数组中查找...
这个"matlab开发-BinarySearch"项目提供了一个名为`bsearch.m`的MATLAB函数,用于在向量中执行二进制查找操作。下面我们将深入探讨二进制搜索的原理、MATLAB实现以及它在数据分析和机器学习中的应用。 二进制搜索的...
1975年,来自斯坦福大学的Jon Louis Bentley在ACM杂志上发表的一篇论文:Multidimensional Binary Search Trees Used for Associative Searching 中正式提出和阐述的了把空间划分为多个部分的k-d树。
### 最优二叉查找树(Optimal Binary Search Tree) #### 概述 最优二叉查找树(Optimal Binary Search Tree, OBST)是计算机科学领域内一种高效的搜索数据结构,其设计目标是在已知各节点访问概率的情况下,构建...
二叉搜索树(Binary Search Tree,BST)是一种特殊类型的二叉树,它的每个节点都包含一个键(key)、一个关联的值、一个指向左子树的引用和一个指向右子树的引用。在二叉搜索树中,对于任意节点,其左子树中的所有...
在这个“BinarySearch_C++_算法_折半查找_”的项目中,我们将会探讨如何使用C++实现这个算法。 首先,我们要明白二分查找的基本思想。假设我们有一个已排序的数组,我们需要查找一个特定值。我们从数组的中间开始...
本项目“matlab开发-Binarysearch”显然聚焦于如何在MATLAB中实现二进制搜索算法。该算法利用分治思想,通过不断缩小搜索范围来定位目标元素,时间复杂度为O(log n),在大数据量的处理中具有显著优势。 `bsearch.m`...
- 在`binarySearch`函数中实现上述的二分搜索逻辑,包括计算中间索引、比较元素和更新边界。 总的来说,二分搜索是计算机科学中一种重要的搜索算法,尤其适用于处理大量有序数据。在C语言中实现二分搜索,可以显著...
二叉搜索树(Binary Search Tree,BST)的实现与操作.docx 二叉搜索树(Binary Search Tree,BST)的实现与操作.docx 二叉搜索树(Binary Search Tree,BST)的实现与操作.docx 二叉搜索树(Binary Search Tree,BST...
int binarySearch(int arr[], int left, int right, int target) { while (left ) { int mid = left + (right - left) / 2; // 计算中间索引,避免整型溢出 if (arr[mid] == target) { // 如果中间元素就是目标...
在Java编程语言中,`binarySearch()`方法是`java.util.Arrays`类的一个静态方法,它采用二分查找算法来高效地在有序数组中查找指定的元素。二分查找是一种在有序数据集合中寻找目标值的算法,其效率远高于线性搜索。...
Binary Search Tree 利用C++實現 Binary Search Tree
最小成本二分检索树optimal binary optimal binary
二叉搜索树(Binary Search Tree,简称BST)是一种在计算机科学中广泛应用的数据结构,它具有以下特性:每个节点包含一个键(key)、一个关联的值、一个指向左子树的引用以及一个指向右子树的引用。在二叉搜索树中,...
实现折半查找的程序 希望大家功能学习,共同进步
在这个例子中,"bstTreeExample_java_binarysearch_" 提供了一个Java实现的二叉搜索树编码器的样本代码,帮助我们理解如何在实际编程中运用这种数据结构。 首先,`BSTlex.java` 文件是源代码,它包含了二叉搜索树的...