Browsed by
分类:搜索

二分搜索 Binary search

二分搜索 Binary search

二分搜索也是比较常见的,在生活中的应用尤其广泛。比如在酒桌上玩猜数字,一个人坐庄先准备一个在一定范围内的数字,其余每个人轮流猜一次,庄说出是大了还是小了,说中的人喝。这个游戏玩过的人应该不少,其中肯定有许多人都是从中间开始猜,认为这样是比较快的排除方法。是的,这就是二分搜索。 二分搜索对于查找对象有要求,即有序。原理就是取其中间进行判断,如果未找到,则根据顺序关系再分别对两边其中的一个子区进行再次查找,直到找到或者未发现,搜索结束。 public static void main(String[] args) { int[] array = {1, 12, 13, 27, 34, 38, 49, 50, 64, 65, 76, 78, 97}; int target = 50; System.out.println(“result index:” + binarySearch(array, target)); } public static int binarySearch(int[] arr, int target) { int startPosition = 0; // 设置搜索的上下界 int endPosition = arr.length – 1; while (startPosition <= endPosition) { // 在搜索过程中,会逐渐缩小搜索范围 int midPosition = (startPosition + endPosition) / 2; // 确定中间…

阅读全文 Read More

顺序搜索 sequential search

顺序搜索 sequential search

顺序搜索是所有搜索算法中,最简单最无脑的,原理就是穷举,一个一个的比对,直到找到为止。所以对于被搜索的对象也没有任何要求,并不像其他的某些算法那样要求有序等等。 public static void main(String[] args) { int[] array = {49, 38, 65, 97, 76, 13, 27, 50, 78, 34, 12, 64, 1}; int target = 50; System.out.println(“result index:” + sequentialSearch(array, target)); } public static int sequentialSearch(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { // 遍历整个数组 if (arr[i] == target) { // 如果找到,则返回对应的下标 return i; } } return -1; // -1表示未找到 }