167_尚硅谷_Go核心编程_二分查找的代码实现.avi原创

那前边呢，我们把这一个二分查找的思路分析了一下，我们现在呢，把二分查找的代码。实现了，也就是说把思路换成代码来，我们一起编写这个代码。好，打开Vs code，那这个地方呢，我们干脆哈，我们新建一个文件夹，好吧，新建一个文件夹叫二分查找，二分查找它个有个专业词叫binary band。Bary fund，我们新建一个文件叫main，顶go。Go。好，前面这一部分呢，代码我们可以通用一下。把它放到这来。写一个总函数对不对，每。包起来。然后呢，我们来写个二分查找的方法，二分查找的这一个什么呢？二分查找的函数。那首先我们在这里先定义一个数组，这个数组呢，我们就不用别的，我们就直接用我们这已经有的一个数组好不好，就这个数组它本身也是个有序数组，对吧，来定一个数组。

有个类型推导，然后呢，它的大小呢，应该是6INCH。粘过来。是六个数吧，123456没问题，六好，然后呢，我们写二分查找的函数function，二分查找呢，它一般这样取名叫binary find好吧，Bary fund里面呢，给我传一个数组进来，当然我们还是老规矩，用什么呀，用。一个指针来接收，这样子呢，就不用进行自考杯了，效率会高很多。那现在这个数组是6INT类型，然后指针没问题吧。好，开始按我们的思路来完成，大家看看，这个思路非常清晰啊。

把这个思路。从这到这儿。呃，干脆整体把这个拿过来好不好？整体把它拿到我们的这个位置来。我为什么要把它拿过来呢？就是让大家感受到这个代码它是怎么一步一步写出来的，如果只只是想给大家一个结果，其实大家都不用。不用看老师的这些东西，你直接直接拿一本书就完了。那个书上会把结果直接告诉你，对吧，那现在呢。我们就按照刚才分析的思路将其实现走一个，既然你这个函数里边要有数组，同时大家看到，因为你你得告诉我这个数组就是这个数组从左边第几个元素开始，从右边的下标开始，从哪个开始找，是不是应该还有两个参数才可以啊。是不是得有啊，所以说我写个left index in，还有一个right index in，另外还有一个就是你要查找的这个数，是不是有一个数叫find value啊，你得体现出来，好，Find value也是个in。

好，那现在呢说了，他说先找到中间这个数的下标好，这句话其实我们已经写好了，拿过来用一下就行。这个呢，就是刚才老师说的，先找到中间的下标。没问题吧？好找到了，找到过后呢，根据刚才的三个思路来开始走。开始判断啊，如果。如果。中间这个下标。它大于指，但是你这样取是不对的，大家都知道，因为你这个A是一个什么呀，是一个指针，所以这样取是取不到我们这个元素的，应该怎么取，先用一个取值符。然后再去取中间这个下标对应的元素，如果这个成立。说明什么说明注意听，如果这个这个成立的话，这说明应该说明我们要查找的这个数可能在，可能在哪里应该在啊，或者叫应该在哪里呢？是在这个。

Left。因为我我现在我我我现在是从小到大啊，大家看清楚了，就说这个地方大于它，你到底是往左边走还是右边找，还跟你这个数组本身的数顺序这个排序有关。因为你我们现在是从小到大，所以说既然你是从小到大，那你中间这个出台大于大于别人，那就应该是向左边找，那就是说应该在left index到哪个之间呢？到mid。减一这个之间。那如果你是从大到小的话，就根号反过来了，对不对？好，那就应该继续调这个函数。是不是这样，这样跳的时候先把这个传进去，这个时候同学们要不要加地字符。

不需要了，因为你本身就是一个指针，你传给这个自己指针当然是可以的，对不对，好，那left index给我放进去。然后左边这应该是米的减一。好，要查找这个数，继续往下面传，写完了。这是第一个，第二种l if。如果说你要查找的这个数，就说中间这个数呢，怎么样小于find value，那说明我们应该往里边找啊。那就说明我们现在要查找的数应该是在mid。加一到right left这个之间，大家想一想是不是这个道理？Right index时间好，这地方你继续传ray继续传，这边呢，就应该传成me的加一。

没问题吧，Me加一，然后右边这个值呢，仍然是保持不变。同样把find的value传过去，还有一种可能性，诶，那就非常OK了，就是if一个是大，一个是小，那只有最后一种可能就是相等，相等的话呢，就说明怎么样找到了。那如果找到了，同学们请思考此时此刻是不是应该提示一句话了，Print f就说找到。找到了下标为多少呢？给我输出来。好，这个地方我们就用一个格式化吧，注意听啊，下边为这个字。那下边具体来说，此时此刻是哪一个值呢？就是密对不对，找完了。但是你这样写完了过后，还有一个没有考虑的，就是什么情况下说明找不到你没有写，刚才老师已经讲了。说如果left index大于right index，那说明找不到了，但是想是不是这个道理，就是你们想象，你们一定要想象这个指针，它在不停的右边这个不停的往这边靠。

而左边呢，向右边靠，那么有一种可能性就是他们最极端的情况下，就是两个合在一起了，那合在一起呢，还可以判断一次。对不对，还可以判断一次，如果判断了，还不就说他们相等，还可以再判断。但是如果。相等还不是的话，这个红红红色的这个线，这个只针继续往左边，绿色往这边，那就出现左边这个大于右边，那肯定就找不到了，能理解吗？好，我先撤回去啊，这为什么是这个条件，大家搞清楚。好，我把这个条件写清楚了。怎么写？如果注意听，就是判断判断这个left index。对啊，Inle是否？

是否是否大于什么呢？Right index，那就是if。如果说left index大于了right index，那告诉大家，非常不幸，就是找不到。Find value。就直接说一句话啊，找不到。找不到的话怎么办呢？就return就完了。就一层一层把它回去，关于这个递归的使用，我在前面是下了大功夫给他讲的啊，这块是有一点技术含量的，大家都好好想，而且二分查找往往会作为一个笔试题，我记得我大学刚刚毕业的时候，这个面试官考的一个查找就是用的二分，当时是在一个unix操作系统下面写的一个C程序来。检测这个二分查照的只是你们现在变成构元了，对不对，好这个就OK，那现在呢，这个写完了，那写完我们来试一试，测试一下吧，测试一把。

好，我们来测一下，那我就调用这个binary fund。那我传第一个，首先把传进去。那儿传进去是不是你这个时候传的应该是个地址吧。因为你这是个数组，而别人接收的是一个数组的指针，所以说你这应该传一个地址来，最先前是不是从这个一到1234这个下边啊那零。这个下标是多少？这个下标是不是就是这个数组的大小减一啊，注意是不是要减一，如果不减一的话，是不是跑到后后边去了。好，然后呢，你要查找的书是哪一个呢？假设要查找1000没问题吧，好同学们，我们运行一下看看效果如何。来CD点点。CD到我们的binary find。好，我们看代码好像哪个地方有有错误。哪里有错误？看这里，On fun OK，这地方是不是少了一个类型推导？

写完了。好，我们现在呢，诶还有错误，看哪里写的mid单词写错了是吧。这个写错了，单词写错了。还有没有什么问题？好，没有报错了，没有报错，我们就来测一下。跑一个go run什么呢？我们的main.go跑起来。我们现在给他传的一个竖式。下标为四。1000，这个时候我们要查到数1000，是不是下边为401234正确，我们再换一个，这次呢，我们找一个。找一看，看他有没有找到。好，应该下标为零。对吧，找到了下标为零正确，好，我们再找一个中间的吧，89。89，好，我们再来执行一小把，看效果。我们发现此时此刻也找到了，我们再写一个找不到的，比如说我这写一个负六。

注意负六在这里面是不是没有啊。没有没有的话呢，同学们，我们来执行一下，我们发现此时此刻它提示我们找不到完全正确，说明我们这个代码是OK的。代码是完全正确的，大家想一想这个代码是怎么完成的啊，这是一步一步，包括我们是分析的思路，全部都给大家写到位了，你们好好去想一想。好，我把这个代码呢给大家整理一下，放到这里来。好，这次因为源代码比较多，我就直接插一个表格，把源代码放过来就可以了，好吧。这是我们的源代码。我复制一下。放到这里来。好，这是源代码，全部在这了。这这个地方包括分析全部都写写完了啊，就是二分查找的代码实现全部放到这了，大家看一下。好，那同学们，那关于我们这个查找的讲解呢，我们就全部给大家介绍完毕，你们要掌握的就是一个顺序查找，还有一个二分查找。

尤其是尤其是这个二分差找一定要把它好好好的理解一下，因为这里面用到一个递归了，所以说难度稍微大了一点。但是这个呢，也是经常作为面试的好同学们，那关于我们高浪里边数组的查找，就先给大家介绍到这里。